Were massive galaxies already in place at high redshift or were they assembled to their total stellar mass only in recent epochs? Trying to quantitatively answer this question is the main goal of the K20 spectroscopic survey that we carried out at the VLT, measuring the redshift of about 500 Ks-selected galaxies. In this paper, we present the first results of this survey and discuss the first constraints on the nature, number density and clustering of EROs, the derivation of the redshift distribution of Ks<20 galaxies and the first results on the evolution of the Ks-band luminosity function. This wealth of observational results is compared to theorethical predictions of semianalytical hierarchical models. The results indicate that, up to z~1-1.5, luminosity evolution provides a satisfactory picture, whereas the strong density evolution required by the current scenarios of hierarchical merging is inconsistent with the observations. The origin of the discrepancy may reside in the incorrect treatment of the baryon assembly, the star formation modes and epoch, and the role of feedback.