Aims: We present a determination of the intrinsic colors and ages of galaxies at very high redshift, in particular old galaxies (OGs) within extremely red objects (EROs). To date, the definition of EROs has been restricted to objects with z < 2.5, however, here we consider objects with the same properties but shifted to higher redshifts (z > 2.5). We therefore, refer to these objects as very high-redshift EROs (Z-EROS, herein). Methods: We analyze 63 550 galaxies selected in the XMM-LSS field. To obtain a reasonably sized sample of EROs, it is essential to consider a very wide area surveys. We identify targets within an area of 0.77 square degrees for which optical to mid-infrared data are available from Subaru, UKIDSS, and Spitzer. We select Z-EROs based on their colors, and then perform a selection of only OGs. One of our novel innovations is to adapt the traditional method of EROs selection based on the filters I and K, to higher redshifts. Using our method, we identify 20 objects that satisfy the conditions required to be Z-EROs/OGs at redshifts 2.5 ≤ z ≤ 3.8 within some conservative constraints of errors in the photometric redshifts. For each of these objects, we calculate the corresponding color at rest (B - V), and estimate their average stellar mass and age by comparing this color with a synthesis model. Results: Our selected galaxies have high stellar masses ( 1011 M&sun;) and are older than 1 Gyr, hence their stellar populations were formed at z ≳ 4.7. After including additional galaxies with z < 2.5 analyzed in a previous paper, we find that the formation epoch depends significantly on the observed redshift and stellar mass {partial t_form{partial t_obs}= -0.9± 0.3 frac{partial t_form{partiallog 10M_*}=-4.8± 1.8 } Gyr. That is, the higher the stellar mass, the lower the age of the Universe at which it was formed. This result appears to conflict with Λ-CDM models that claim that the most massive galaxies formed after lower mass.