Ruthenium nanocrystals with both a face-centered cubic (fcc) structure and well-controlled facets are attractive catalytic materials for various reactions. Here we report a simple method for the synthesis of Ru octahedral nanocrystals with an fcc structure and an edge length of 9 nm. The success of this synthesis relies on the use of 4.5 nm Rh cubes as seeds to facilitate the heterogeneous nucleation and overgrowth of Ru atoms. We choose Rh because it can resist oxidative etching under the harsh conditions for Ru overgrowth, it can be readily prepared as nanocubes with edge lengths less than 5 nm, and its atoms have a size close to that of Ru atoms. During the seed-mediated growth, the atomic packing of Ru overlayers follows an fcc lattice, in contrast to the conventional hexagonal close-packed (hcp) lattice associated with bulk Ru. The final product takes an octahedral shape, with the surface enclosed by {111} facets. Our in situ measurements suggest that both the octahedral shape and the fcc crystal structure can be well preserved up to 400 degrees C, which is more than 100 degrees C higher than what was reported for Ru octahedral nanocages. When utilized as catalysts, the Ru octahedral nanocrystals exhibited 4.4-fold enhancement in terms of specific activity toward oxygen evolution relative to hcp-Ru nanoparticles. We also demonstrate that Ru{111} facets are more active than Ru{100} facets in catalyzing the oxygen evolution reaction. Altogether, this work offers an effective method for the synthesis of Ru nanocrystals with an fcc structure and well-defined {111} facets, as well as enhanced thermal stability and catalytic activity. We believe these nanocrystals will find use in various catalytic applications.