Using the IRAM NOrthern Extended Millimeter Array (NOEMA), we conducted a program to measure redshifts for 13 bright galaxies detected in the Herschel Astrophysical Large Area Survey (H-ATLAS) with $S_{500{mu}rm m}ge$80 mJy. We report reliable spectroscopic redshifts for 12 individual sources, which are derived from scans of the 3 and 2 mm bands, covering up to 31 GHz in each band, and are based on the detection of at least two emission lines. The spectroscopic redshifts are in the range $2.08<z<4.05$ with a median value of $z=2.9pm$0.6. The sources are unresolved or barely resolved on scales of 10 kpc. In one field, two galaxies with different redshifts were detected. In two cases the sources are found to be binary galaxies with projected distances of ~140 kpc. The linewidths of the sources are large, with a mean value for the full width at half maximum of 700$pm$300 km/s and a median of 800 km/s. We analyse the nature of the sources with currently available ancillary data to determine if they are lensed or hyper-luminous $L_{rm FIR} > 10^{13},L_odot$ galaxies. We also present a reanalysis of the spectral energy distributions including the continuum flux densities measured at 3 and 2 mm to derive the overall properties of the sources. Future prospects based on these efficient measurements of redshifts of high-z galaxies using NOEMA are outlined, including a comprehensive survey of all the brightest Herschel galaxies.