Globular clusters are some of the oldest bound stellar structures observed in the Universe(1). They are ubiquitous in large galaxies and are believed to trace intense star-formation events and the hierarchical build-up of structure(2,3). Observations of globular clusters in the Milky Way, and a wide variety of other galaxies, have found evidence for a'metallicity floor', whereby no globular clusters are found with chemical (metal) abundances below approximately 0.3 to 0.4 per cent of that of the Sun(4-6). The existence of this metallicity floor may reflect a minimum mass and a maximum redshift for surviving globular clusters to form-both critical components for understanding the build-up of mass in the Universe(7). Here we report measurements from the Southern Stellar Streams Spectroscopic Survey of the spatially thin, dynamically cold Phoenix stellar stream in the halo of the Milky Way. The properties of the Phoenix stream are consistent with it being the tidally disrupted remains of a globular cluster. However, its metal abundance ([Fe/H] = -2.7) is substantially below the empirical metallicity floor. The Phoenix stream thus represents the debris of the most metal-poor globular clusters discovered so far, and its progenitor is distinct from the present-day globular cluster population in the local Universe. Its existence implies that globular clusters below the metallicity floor have probably existed, but were destroyed during Galactic evolution. The Phoenix stream in the Milky Way halo is shown to be a tidally disrupted remnant of an unusually metal-poor globular cluster, which was possibly destroyed during Galactic evolution.