We use the deep NIR imaging of the FIRES survey to investigate trends with redshift of the properties of galaxies selected to have strong Balmer/4000 angstrom breaks at 2 < z < 4.5. Analogous to the J - K > 1.3 (AB) color criterion designed to select red galaxies at z > 2, we propose two color criteria, J - H > 0.9 and H - K > 0.9, to select red galaxies in two redshift bins at 2 < z < 3 and 2 < z < 4.5, respectively. From the FIRES catalogs of the HDF-S (4.7 arcmin(2)) and MS 1054-3 (26.3 arcmin(2)) fields, we find 18 galaxies with [z(phot)] = 2.4 that satisfy, J(s) - H > 0.9, H < 23.4 and 23 galaxies with [z(phot)] = 3.7 that satisfy H - K-s > 0.9, K-s < 24.6, where the flux limits are chosen to match the limiting rest-frame luminosities at the different median redshifts of the two samples. The space densities of the J(s) - H and H - K-s samples are (1.5 +/- 05) x 10-4 and (1.2 +/- 0.4) x 10(-4) Mpc(-3), respectively. The rest-frame U - B colors of galaxies in both samples are similarly red (as expected from the definition of the color criteria), but the rest-frame UV properties are different: galaxies in the higher redshift H - K-s selected sample have blue NUV-optical colors and UV slopes similar to those of Lyman break galaxies, while the J(s) - H galaxies are generally red over the entire wavelength range observed. Synthetic template fits indicate that the distinct rest-NUV properties of the two samples are primarily a result of dust: we find [A(V)](JH) = 1 mag and [A(V)](HK) = 0.2 mag. The median stellar mass determined from the template fits decreases by a factor of similar to 5 from z = 2.4 to 3.7, which, coupled with the fact that the space density of such galaxies remain roughly constant, may imply that the stellar mass density in red galaxies decreases by a similar factor over this redshift range.
