We report the first self–assembled growth of dislocation-free, highly uniform, <I>tensile-strained</I> III-V nanostructures on a (110) surface. Devices fabricated on the (110) plane of III-V semiconductors could have several advantages over their (001) surface counterparts. Due to suppression of the in-plane Dresselhaus field, carrier spin-lifetimes in (110)-oriented quantum wells can be significantly longer than in equivalent (001)-oriented structures. Additionally, spin-lifetimes can be lengthened by carrier confinement within self-assembled quantum dots (SAQDs). Incorporating the attractive properties of (110) surfaces with SAQDs is expected therefore to lead to novel devices with potentially very long spin-lifetimes. Long spin-lifetime is a fundamental requirement for many spintronic applications. Driven by compressive strain, SAQDs are readily formed in the well-established InAs/GaAs(001) and Ge/Si(001) systems. In contrast, deposition of compressive materials on other low-index surfaces such as (110) typically results in heavily dislocated two-dimensional films. Achieving the combination of SAQDs with a (110) surface has thus been highly challenging. However, analyses of dislocation energetics and kinetics indicate that the strain relaxation behavior of (001)-oriented material can be replicated on (110) surfaces provided the <I>direction of strain</I> is inverted. As such, by analogy to compressively strained SAQDs on (001) surfaces, sufficient <I>biaxial tension</I> could result in the self-assembly of dislocation-free nanostructures on (110)-oriented material. To establish the validity of this prediction, we used molecular beam epitaxy to deposit tensile-strained GaP on GaAs(110) surfaces. We discovered that GaP spontaneously forms three-dimensional nanostructures at terrace edges on the GaAs surface. Straightforward control of nanostructure size is demonstrated without the bimodality encountered in (001) SAQDs. The nanostructures exhibit high shape and size uniformity, with smaller dots showing no evidence of dislocations in cross-sectional transmission electron microscopy. Tuning of the growth parameters enables control of nanostructure density. No wetting-layer is observed prior to dot formation, which implies a Volmer-Weber growth-mode for the GaP nanostructures. This study represents a proof of concept for self-assembled growth driven by tensile strain on a (110) surface. It is anticipated that this will form the first step towards a more general description of epitaxial nanostructure self-assembly.  V. Sih et al., <I>Nat Phys</I> 1, 31 (2005).  G.M. Müller et al., <I>Phys. Rev. Lett.</I> 101, 206601 (2008).  L.M. Woods et al., <I>Phys. Rev. B</I> 66, 161318 (2002).  B.A. Joyce and D.D. Vvedensky, <I>Mat. Sci. & Eng. R</I> 46, 127 (2004).  E.P. Kvam and R. Hull, <I>J. Appl. Phys.</I> 73, 7407 (1993).