We have analysed five-epoch Great Observatories Origins Deep Survey (GOODS) HST-ACS B, V, I775 and z data sets (v. 1.0 release), in conjunction with existing VLT-ISAAC imaging in the J, H and Ks bands, to derive estimated redshifts for the sample of 198 extremely red galaxies (ERGs) with Ks <22 (Vega) and (I775-Ks) > 3.92 selected by Roche, Dunlop & Almaini (2003) from 50.4 arcmin2 of the GOODS/Chandra Deep Field South. We find that, at this depth, the ERG population spans the redshift range 0.5 <zphot <4.75 and over two decades in mass (~3 × 109 Msolar to ~3 × 1011 Msolar). Our results show that the dust-corrected red envelope of galaxy evolution is well modelled by a starburst at redshift zf= 5 followed thereafter by passive evolution. We explore the evolution of the ERG luminosity function (LF) from redshifts = 1.0 to = 2.5 and compare it with the global Ks-band LF at redshifts 1 <zphot <2. We find that the bright end of the ERG LF does not decrease from redshifts = 2.0 to = 2.5 and we connect this fact with the presence of progenitors of the local L > L* population at redshifts zphot > 2. We determine lower limits of ρc= (6.1 +/- 1.9) × 10-5 Mpc-3 and ρc= (2.1 +/- 1.1) × 10-5 Mpc-3 on the comoving densities of progenitors of local massive galaxies already assembled at redshifts = 2.5 and = 3.5, respectively. We have investigated the existence of high-redshift Lyman-break galaxies massive enough to be included in this ERG sample. Out of an initial list of 12 potential very high redshift candidates, we have identified two ERGs which have a high probability of lying at zphot > 4. We discuss the advantages of multicolour to single-colour selection techniques in obtaining reliable lists of very high redshift candidate sources, and present revised lower redshift estimates for sources previously claimed as potential z > 5 dropouts in recent studies.