We present a comparative study of the growth of tensile-strained GaP on the four low-index surfaces of GaAs: (001), (110), (111)A, and (111)B. For each surface orientation we outline the growth conditions required for smooth GaAshomoepitaxy. We are able to predict the resulting surface morphology when GaP is deposited onto these four GaAssurfaces by considering the influence of surface orientation on tensile strain relief. GaP deposited on GaAs(001) forms extremely smooth, planar layers. In contrast, the elastic relief of tensile strain on both GaAs(110) and GaAs(111)A leads to the three-dimensional self-assembly of GaP into dislocation-free nanostructures. Similarities between tensile and compressive self-assembly suggest that the kinetics governing many aspects of self-assembledgrowth is independent of the sign of strain. We show that differences in self-assembly on GaAs(110) and (111)A are the result of unequal adatom diffusion lengths. Tensile-strained self-assembly also occurs on GaAs(111)B, although our use of misoriented substrates resulted in the formation of one-dimensional nanoscale wires. Tensile-strained self-assembly is a versatile, reliable technique that can be extended to a wide range of materials in order to create dislocation-free nanostructures on (110) and (111) surfaces.