Using the IRAM NOrthern Extended Millimetre Array (NOEMA), we conducted a Large Programme (z-GAL) to measure redshifts for 126 bright galaxies detected in the Herschel Astrophysical Large Area Survey (H-ATLAS), the HerMES Large Mode Survey (HeLMS), and the Herschel Stripe 82 (HerS) Survey. We report reliable spectroscopic redshifts for a total of 124 of the Herschel-selected galaxies. The redshifts are estimated from scans of the 3 and 2-mm bands (and, for one source, the 1-mm band), covering up to 31 GHz in each band, and are based on the detection of at least two emission lines. Together with the Pilot Programme, where 11 sources had their spectroscopic redshifts measured, our survey has derived precise redshifts for 135 bright Herschel-selected galaxies, making it the largest sample of high-z galaxies with robust redshifts to date. Most emission lines detected are from 12CO (mainly from J = 2-1 to 5-4), with some sources seen in [CI] and H2O emission lines. The spectroscopic redshifts are in the range 0.8 < z < 6.55 with a median value of z = 2.56 ± 0.10, centred on the peak epoch of galaxy formation. The linewidths of the sources are large, with a mean value for the full width at half maximum ΔV of 590 ± 25 km s−1 and with 35% of the sources having widths of 700 km s−1 < ΔV < 1800 km s−1. Most of the sources are unresolved or barely resolved on scales of ∼2 to 3″ (or linear sizes of ∼15 − 25 kpc, unlensed). Some fields reveal double or multiple sources in line emission and the underlying dust continuum and, in some cases, sources at different redshifts. Taking these sources into account, there are, in total, 165 individual sources with robust spectroscopic redshifts, including lensed galaxies, binary systems, and over-densities. This paper presents an overview of the z-GAL survey and provides the observed properties of the emission lines, the derived spectroscopic redshifts, and a catalogue of the entire sample. The catalogue includes, for each source, the combined continuum and emission lines' maps together with the spectra for each of the detected emission lines. The data presented here will serve as a foundation for the other z-GAL papers in this series reporting on the dust emission, the molecular and atomic gas properties, and a detailed analysis of the nature of the sources. Comparisons are made with other spectroscopic surveys of high-z galaxies and future prospects, including dedicated follow-up observations based on these redshift measurements, are outlined.