We present the results of our systematic search for the reddest far-infrared (FIR) and submillimeter (sub-mm) galaxies using the data from the Herschel Multi-tiered Extragalactic Survey (HerMES) and the SCUBA2 Cosmological Legacy Survey (S2CLS). The red FIR galaxies are "500{mu}m risers," whose spectral energy distributions increase with wavelength across the three FIR passbands of the Spectral and Photometric Imaging REceiver (SPIRE) of Herschel. Within 106.5deg^2^ of the HerMES fields, we have selected 629 500{mu}m risers. The red sub-mm galaxies are "SPIRE drop-outs," which are prominent detections in the S2CLS 850{mu}m data but are extremely weak or invisible in the SPIRE bands. Within the 2.98deg^2^ common area of HerMES and S2CLS, we have selected 95 such objects. These very red sources could be dusty starbursts at high redshifts (z>~4-6) because the peak of their cold-dust emission heated by star formation is shifted to the reddest FIR/sub-mm bands. The surface density of 500{mu}m risers is ~8.2deg^-2^ at the >=20mJy level in 500{mu}m, while that of SPIRE drop-outs is ~19.3deg^-2^ at the >=5mJy level in 850{mu}m. Both types of objects could span a wide range of redshifts, however. Using deep radio data in these fields to further select the ones likely at the highest redshifts, we find that the surface density of z>6 candidates is 5.5deg^-2^ among 500{mu}m risers and is 0.8-13.6deg^-2^ among SPIRE drop-outs. If this is correct, the dust-embedded star formation processes in such objects could contribute comparably as Lyman-break galaxies to the global SFR density at z>6.