A significant fraction (30 per cent) of well-localized short gamma-ray bursts (sGRBs) lack a coincident host galaxy. This leads to two main scenarios: (i) that the progenitor system merged outside of the visible light of its host, or (ii) that the sGRB resided within a faint and distant galaxy that was not detected by follow-up observations. Discriminating between these scenarios has important implications for constraining the formation channels of neutron star mergers, the rate and environments of gravitational wave sources, and the production of heavy elements in the Universe. In this work, we present the results of our observing campaign targeted at 31 sGRBs that lack a putative host galaxy. Our study effectively doubles the sample of well-studied sGRB host galaxies, now totaling 72 events of which $28{{\ \rm per\ cent}}$ lack a coincident host to deep limits (r ≳ 26 or F110W ≳ 27 AB mag), and represents the largest homogeneously selected catalogue of sGRB offsets to date. We find that 70 per cent of sub-arcsecond localized sGRBs occur within 10 kpc of their host's nucleus, with a median projected physical offset of 5.6 kpc. Using this larger population, we discover an apparent redshift evolution in their locations: bursts at low-z occur at 2 × larger offsets compared to those at z > 0.5. This evolution could be due to a physical evolution of the host galaxies themselves or a bias against faint high-z galaxies. Furthermore, we discover a sample of hostless sGRBs at z ≳ 1 that are indicative of a larger high-z population, constraining the redshift distribution and disfavoring lognormal delay time models.