ABSTRACT Until recently, only a handful of dusty, star-forming galaxies (DSFGs) were known at z > 4, most of them significantly amplified by gravitational lensing. Here, we have increased the number of such DSFGs substantially, selecting galaxies from the uniquely wide 250, 350, and 500 m Herschel-ATLAS imaging survey on the basis of their extremely red far-infrared colors and faint 350 and 500 m flux densities, based on which, they are expected to be largely unlensed, luminous, rare, and very distant. The addition of ground-based continuum photometry at longer wavelengths from the James Clerk Maxwell Telescope and the Atacama Pathfinder Experiment allows us to identify the dust peak in their spectral energy distributions (SEDs), with which we can better constrain their redshifts. We select the SED templates that are best able to determine photometric redshifts using a sample of 69 high-redshift, lensed DSFGs, then perform checks to assess the impact of the CMB on our technique, and to quantify the systematic uncertainty associated with our photometric redshifts, = 0.14 (1 + z), using a sample of 25 galaxies with spectroscopic redshifts, each consistent with our color selection. For Herschel-selected ultrared galaxies with typical colors of S500/S250 ∼ 2.2 and S500/S350 ∼ 1.3 and flux densities, S500 ∼ 50 mJy, we determine a median redshift, , an interquartile redshift range, 3.30-4.27, with a median rest-frame 8-1000 m luminosity, , of 1.3 × 1013 L . A third of the galaxies lie at z > 4, suggesting a space density, z > 4, of 6 × 10−7 Mpc−3. Our sample contains the most luminous known star-forming galaxies, and the most overdense cluster of starbursting proto-ellipticals found to date.