We have analysed a sample of 574 Spitzer 4.5 micron-selected galaxies with [4.5]<23 and Ks_auto>24 (AB) over the UltraVISTA ultra-deep COSMOS field. Our aim is to investigate whether these mid-IR bright, near-IR faint sources contribute significantly to the overall population of massive galaxies at redshifts z>=3. By performing a spectral energy distribution (SED) analysis using up to 30 photometric bands, we have determined that the redshift distribution of our sample peaks at redshifts z~2.5-3.0, and ~32% of the galaxies lie at z>=3. We have studied the contribution of these sources to the galaxy stellar mass function (GSMF) at high redshifts. We found that the [4.5]<23, Ks_auto>24 galaxies produce a negligible change to the GSMF previously determined for Ks_auto<24 sources at 3=<z<4, but their contribution is more important at 4=<z<5, accounting for >~50% of the galaxies with stellar masses Mst>~6 x 10^10 Msun. We also constrained the GSMF at the highest-mass end (Mst>~2 x 10^11 Msun) at z>=5. From their presence at 5=<z<6, and virtual absence at higher redshifts, we can pinpoint quite precisely the moment of appearance of the first most massive galaxies as taking place in the ~0.2 Gyr of elapsed time between z~6 and z~5. Alternatively, if very massive galaxies existed earlier in cosmic time, they should have been significantly dust-obscured to lie beyond the detection limits of current, large-area, deep near-IR surveys.