The shape-controlled synthesis of noble metal nanocrystals (NCs) bounded by high-index facets is a current research interest because the products have the potential of significantly improving the catalytic performance of NCs in industrially important reactions. This study reports a versatile method for synthesizing polyhedral NCs enclosed by a variety of high-index Pd facets. The method is based on the heteroepitaxial growth of Pd layers on concave trisoctahedral (TOH) gold NC seeds under careful control of the growth kinetics. Polyhedral Au@Pd NCs with three different classes of high-index facets, including concave TOH NCs with {hhl} facets, concave hexoctahedral (HOH) NCs with {hkl} facets, and tetrahexahedral (THH) NCs with {hk0} facets, can be formed in high yield. The Miller indices of NCs are also modifiable, and we have used the THH NCs as a demonstrative example. The catalytic activities of these NCs were evaluated by the structure-sensitive reaction of formic acid electro-oxidation. The results showed that the high-index facets are generally more active than the low-index facets. In summary, a seeded growth process based on concave high-index faceted monometallic TOH NC templates and careful control of the growth kinetics is a simple and effective strategy for the synthesis of noble metal NCs with high-index facets. It also offers tailorability of the surface structure in shape-controlled synthesis.