We have analysed a sample of 574 Spitzer 4.5 \mu m -selected galaxies with [ 4.5 ] < 23 and K _ { s } ^ { 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 \geq 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 \approx 2.5 - 3.0 , and \sim 32 \% of the galaxies lie at z \geq 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 , K _ { s } ^ { auto } > 24 galaxies produce a negligible change to the GSMF previously determined for K _ { s } ^ { auto } < 24 sources at 3 \leq z < 4 , but their contribution is more important at 4 \leq z < 5 , accounting for \raisebox { -3.698858 pt } { ~ { } \shortstack { $ > $ \ [ -0.07 cm ] $ \sim$ } } ~ { } 50 \% of the galaxies with stellar masses M _ { st } \raisebox { -3.698858 pt } { ~ { } \shortstack { $ > $ \ [ -0.07 cm ] $ \sim$ } } ~ { } 6 \times 10 ^ { 10 } M _ { \odot } . We also constrained the GSMF at the highest-mass end ( M _ { st } \raisebox { -3.698858 pt } { ~ { } \shortstack { $ > $ \ [ -0.07 cm ] $ \sim$ } } ~ { } 2 \times 10 ^ { 11 } M _ { \odot } ) at z \geq 5 . From their presence at 5 \leq 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 \sim 0.2 Gyr of elapsed time between z \sim 6 and z \sim 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 .