  We present a method for selecting $z>4$ dusty, star forming galaxies (DSFGs)
using Herschel/SPIRE 250/350/500 $\mu m$ flux densities to search for red
sources. We apply this method to 21 deg$^2$ of data from the HerMES survey to
produce a catalog of 38 high-$z$ candidates. Follow-up of the first 5 of these
sources confirms that this method is efficient at selecting high-$z$ DSFGs,
with 4/5 at $z=4.3$ to $6.3$ (and the remaining source at $z=3.4$), and that
they are some of the most luminous dusty sources known. Comparison with
previous DSFG samples, mostly selected at longer wavelengths (e.g., 850 $\mu
m$) and in single-band surveys, shows that our method is much more efficient at
selecting high-$z$ DSFGs, in the sense that a much larger fraction are at
$z>3$. Correcting for the selection completeness and purity, we find that the
number of bright ($S_{500\,\mu m} \ge 30$ mJy), red Herschel sources is $3.3
\pm 0.8$ deg$^{-2}$. This is much higher than the number predicted by current
models, suggesting that the DSFG population extends to higher redshifts than
previously believed. If the shape of the luminosity function for high-$z$ DSFGs
is similar to that at $z\sim2$, rest-frame UV based studies may be missing a
significant component of the star formation density at $z=4$ to $6$, even after
correction for extinction.
