Hercules X-1 is one of the best studied highly magnetised neutron star X-ray binaries with a wealth of archival data. We present the discovery of an ionised wind in its X-ray spectrum when the source is in the high state. The wind detection is statistically significant in most of the XMM-Newton observations, with velocities ranging from 200 to 1000 km/s. Observed features in the iron K band can be explained by both wind absorption or by a forest of iron emission lines. However, we also detect nitrogen, oxygen and neon absorption lines at the same systematic velocity in the high-resolution RGS grating spectra. The wind must be launched from the accretion disc, and could be the progenitor of the UV absorption features observed at comparable velocities, but the latter likely originate at significantly larger distances from the compact object. We find strong correlations between the ionisation level of the outflowing material and the ionising luminosity as well as the super-orbital phase. If the luminosity is driving the correlation, the wind could be launched by a combination of Compton heating and radiation pressure. If instead the super-orbital phase is the driver for the variations, the observations are likely scanning the wind at different heights above the warped accretion disc. If this is the case, we can estimate the wind mass outflow rate, corrected for the limited launching solid angle, to be roughly 70% of the mass accretion rate.