We present the galaxy rest-frame near-IR Luminosity Function (LF) and its cosmic evolution to z=1.5 based on a spectroscopic survey of a magnitude limited sample of galaxies with Ks<20 (the K20 survey, Cimatti et al. 2002b). The LFs have been derived in the rest-frame J and Ks bands using 3 z bins (z_mean= 0.5, 1, 1.5) and compared to the local near-IR LF. 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 z<1.3. Viceversa, the density of luminous galaxies (M_Ks-5logh_70<-25.5) is higher than locally at all z and relatively constant or mildly increasing with z within our sample. The data are consistent with a mild luminosity evolution both in the J and Ks-band up to z=1.5 (DeltaM_J=-0.69+-0.12 and DeltaM_K=-0.54+-0.12 at z=1). 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 (<30%) up to z=1, thus suggesting that massive elliptical galaxies were already in place at z=1 and they should have formed their stars and assembled their mass at higher z. There appears to be a correlation of the optical/near-IR colors with near-IR luminosities, the most luminous/massive galaxies being red/old. We find a slow evolution with z of the near-IR comoving luminosity density to z=1.5. Finally, we show that hierarchical models overpredict significantly the density of low luminosity galaxies at z<=1 and underpredict the density of luminous galaxies at z>=1, whereas PLE models are more consistent with the data up to z=1.5. The GIF model (Kaufmann et al. 1999) shows a clear deficiency of red luminous galaxies at z=1 compared to our observations and predicts a decrease of luminous galaxies with z not observed in our sample.