We have examined the formation mechanisms of a variety of semiconductor nanostructures, including phase separation-induced alloy nanostructures and strain-induced self-assembled quantum dots. Using data from cross-sectional scanning tunneling microscopy, in conjunction with X-ray reciprocal space maps, we have developed new models for self-ordering of InAs/GaAs quantum dot superlattices and spontaneous lateral phase separation in InAlAs alloys. These models are likely to be applicable to a wide range of heteroepitaxial semiconductor nanostructures.