Core-shell nanoparticles often have unique physical, chemical, magnetic, and optical properties, but provide challenges in processing/formation. Here, we show that core-shell nanoparticles can form naturally, in one step, during gas-phase condensation in immiscible systems with appropriate differences in surface energies of the constituent materials. While a large difference in surface energy and positive ΔHmix is the ideal scenario for core-shell formation, the dominance of surface energy at the nanoscale can be used to create core-shell structures in systems that have either zero or small but negative enthalpies of mixing. Additionally, a critical size exists below which the nanoclusters consist of solid solutions, even in systems with positive ΔHmix, and above which the core-shell structure occurs. Thus, core-shell structures can be engineered in many inorganic systems, with tailored functional properties.