Nanoheteroepitaxy is a fundamentally new epitaxial approach that utilizes three-dimensional stress relief mechanisms available to nanoscale heterostructures to eliminate defects provided the island diameter is below a critical value 2l(c),. Analysis shows that 2l(c)similar to (15-30)X the critical thickness h(c). In the case of GaAs on Si (similar to4% misfit), 2l(c)similar to 40nm. In material systems such as GaN on Si (similar to 20% misfit), where the misfit is much larger and interfacial defects are unavoidable, the nanoheteroepitaxial structure is shown to reduce the formation and propagation of threading defects. Nanostructured substrate parameters that impact growth are discussed and interferometric lithography is introduced as a method for fabrication of large-area substrates for nanoheteroepitaxy, Si nanoisland diameters as small as 20 nm are demonstrated. Scanning and transmission electron microscopy data of GaN grown on Si (iiia organometallic vapor phase epitaxy) shows reduced threading defects in nanostructured samples compared to growth on planar substrates. Photoluminescence intensity data of nanostructured samples is enhanced by similar to 100X as compared to planar-growth samples.