We present 1.3- and/or 3-mm continuum images and 3-mm spectral scans, obtained using Northern Extended Millimeter Array (NOEMA) and Atacama Large Millimeter Array (ALMA), of 21 distant, dusty, star-forming galaxies. Our sample is a subset of the galaxies selected by Ivison et al. on the basis of their extremely red far-infrared (far-IR) colours and low Herschel flux densities; most are thus expected to be unlensed, extraordinarily luminous starbursts at z ≳ 4, modulo the considerable cross-section to gravitational lensing implied by their redshift. We observed 17 of these galaxies with NOEMA and four with ALMA, scanning through the 3-mm atmospheric window. We have obtained secure redshifts for seven galaxies via detection of multiple CO lines, one of them a lensed system at z = 6.027 (two others are also found to be lensed); a single emission line was detected in another four galaxies, one of which has been shown elsewhere to lie at z = 4.002. Where we find no spectroscopic redshifts, the galaxies are generally less luminous by 0.3–0.4 dex, which goes some way to explaining our failure to detect line emission. We show that this sample contains the most luminous known star-forming galaxies. Due to their extreme star-formation activity, these galaxies will consume their molecular gas in ≲ 100 Myr, despite their high molecular gas masses, and are therefore plausible progenitors of the massive, ‘red-and-dead’ elliptical galaxies at z ≈ 3.