The basic physics of nucleation in solid single-crystal nanoparticles is revealed by a phase-field theory that includes surface energy, chemical reactions, and coherency strain. In contrast to binary fluids, which form arbitrary contact angles at surfaces, complete "wetting" by one phase is favored at binary solid surfaces. Nucleation occurs when surface wetting becomes unstable, as the chemical energy gain (scaling with area) overcomes the elastic energy penalty (scaling with volume). The nucleation barrier thus decreases with the area-to-volume ratio and vanishes below a critical size. Thus nanoparticles tend to transform in order of increasing size, leaving the smallest particles homogeneous (in the phase of lowest surface energy). The model is used to simulate phase separation in realistic nanoparticle geometries for LiXFePO4, a popular cathode material for Li-ion batteries, and collapses disparate experimental data for the nucleation barrier with no adjustable parameters. Beyond energy storage, the theory shows how to tailor the elastic and surface properties of a solid nanostructure to achieve desired phase behavior.