By using octahedral gold nanocrystals with sizes of approximately 50 nm as the structure-directing cores for the overgrowth of Pd shells, Au-Pd core-shell heterostructures with systematic shape evolution can be directly synthesized. Core-shell octahedra, truncated octahedra, cuboctahedra, truncated cubes, and concave cubes were produced by progressively decreasing the amount of the gold nanocrystal solution introduced into the reaction mixture containing cetyltrimethylammonium bromide (CTAB), H2PdCl4, and ascorbic acid. The core-shell structure and composition of these nanocrystals has been confirmed. Only the concave cubes are bounded by a variety of high-index facets. This may be a manifestation of the release of lattice strain with their thick shells at the corners. Formation of the [CTA] 2[PdBr4] complex species has been identified spectroscopically. Time-dependent UV-vis absorption spectra showed faster Pd source consumption rates in the growth of truncated cubes and concave cubes, while a much slower reduction rate was observed in the generation of octahedra. The concave cubes and octahedra were used as catalysts for a Suzuki coupling reaction. They can all serve as effective and recyclable catalysts, but the concave cubes gave higher product yields with a shorter reaction time attributed to their high-index surface facets. The concave cubes can also catalyze a wide range of Suzuki coupling reactions using aryl iodides and arylboronic acids with electron-donating and -withdrawing substituents. © 2011 American Chemical Society.