We present the galaxy rest-frame near-IR Luminosity Function (LF) and its cosmic evolution to based on a spectroscopic survey of a magnitude limited sample of galaxies with (the K20 survey, Cimatti et al. 2002b). The LFs have been derived in the rest-frame J and Ks bands. Their evolution is traced using three different redshift bins () and comparing them to the Local near-IR Luminosity Function. The luminosity functions at different redshifts are fairly well fitted by Schechter functions at . The faint-end of the LFs () is consistent with the local estimates, with no evidence for a change either in the slope or normalization up to . At higher redshift this part of the luminosity function is not well sampled by our data. Viceversa, the density of luminous galaxies () is higher than locally at all redshifts and relatively constant or mildly increasing with redshift within our sample. The data are consistent with a mild luminosity evolution both in the J- and Ks-band up to , with an amplitude of about and at . Pure density evolution is not consistent with the observed LF at . Moreover, we find that red and early-type galaxies dominate the bright-end of the LF, and that their number density shows at most a small decrease (< ) up to , thus suggesting that massive elliptical galaxies were already in place at and they should have formed their stars and assembled their mass at higher redshift. There appears to be a correlation of the optical/near-IR colors with near-IR luminosities, the most luminous/massive galaxies being red/old, the low-luminous galaxies being instead dominated by blue young stellar populations. We also investigate the evolution of the near-IR comoving luminosity density to , finding a slow evolution with redshift ( with and ). Finally, we compare the observed LFs with the predictions of a set of the most updated hierarchical merging models. Such a comparison shows that the current versions of hierarchical models overpredict significantly the density of low luminosity galaxies at and underpredict the density of luminous galaxies at , whereas passive evolution models are more consistent with the data up to . The GIF model (Kaufmann et al. 1999) shows a clear deficiency of red luminous galaxies at compared to our observations and predicts a decrease of luminous galaxies with redshift not observed in our sample.