We present novel structures produced by solid-phase crystallization, a process where catalytic nanoparticles are grown from the "inside-out" by phase-segregation in the solid phase from within a mixed-metal oxide precursor. Such a process has been shown by us to greatly extend the stability and lifetime of catalysts owing to the stronger interface between the catalyst and support. Despite this finding, if one were only able to use this technique to grow homogenously structured nanoparticles, it would severely limit its application as such a large number of thermochemical and electrochemical processes exploit heterogeneous structures. We are the first group to show that solid-phase crystallization can be used to synthesize heterostructured nanoparticles such as metallic core-shell particles. In this work, we show three novel techniques for synthesizing heterostructured nanocatalysts using the solid-phase crystallization process. We exploit the effects of differential bond strength, depletion,and surface segregation to create core-shell structures.