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 3
8 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 $zsim2$, 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.
