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-$mu$m Herschel-ATLAS imaging survey on the basis of their extremely red far-infrared colors and faint 350- and 500-$mu$m flux densities - ergo they are expected to be largely unlensed, luminous, rare and very distant. The addition of ground-based continuum photometry at longer wavelengths from the JCMT and APEX allows us to identify the dust peak in their SEDs, better constraining their redshifts. We select the SED templates 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, $sigma=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 $S_{500}/S_{250}sim 2.2$ and $S_{500}/S_{350}sim 1.3$ and flux densities, $S_{500}sim 50,$mJy, we determine a median redshift, $hat{z}_{rm phot}=3.66$, an interquartile redshift range, 3.30$-$4.27, with a median rest-frame 8$-$1000-$mu$m luminosity, $hat{L}_{rm IR}$, of $1.3times 10^{13},$L$_odot$. A third lie at $z>4$, suggesting a space density, $rho_{z>4}$, of $approx 6 times 10^{-7},$Mpc$^{-3}$. Our sample contains the most luminous known star-forming galaxies, and the most over-dense cluster of starbursting proto-ellipticals yet found.