We present the rest-frame Js- and Ks-band luminosity function (LF) of a sample of about 300 galaxies selected in the Hubble Deep Field-South (HDF-S) at Ks≤ 23 (Vega). We use calibrated photometric redshift together with spectroscopic redshift for 25 per cent of the sample. The accuracy reached in the photometric redshift estimate is 0.06 (rms) and the fraction of outliers is 1 per cent. We find that the rest-frame Js-band luminosities obtained by extrapolating the observed Js-band photometry are consistent with those obtained by extrapolating the photometry in the redder H and Ks bands closer to the rest-frame Js, at least up to z∼ 2. Moreover, we find no significant differences among the luminosities obtained with different spectral libraries. Thus, our LF estimate is not dependent either on the extrapolation made on the best-fitting template or on the library of models used to fit the photometry. The selected sample has allowed us to probe the evolution of the LF in the three redshift bins [0; 0.8), [0.8; 1.9) and [1.9; 4) centred at the median redshift zm≃[0.6, 1.2, 3] and to probe the LF at zm≃ 0.6 down to the unprecedented faint luminosities M≃−13 and M≃−14. We find hints of a rise of the faint-end (M> −17 and M> −18) near-infrared (near-IR) LF at zm∼ 0.6: a rise that cannot be probed at higher redshift with our sample. The values of we estimate are consistent with the local value and do not show any trend with redshift. We do not see evidence of evolution from z= 0 to zm∼ 0.6 suggesting that the population of local bright galaxies was already formed at z < 0.8. In contrast, we clearly detect an evolution of the LF to zm∼ 1.2 characterized by a brightening of M* and by a decline of φ*. To zm∼ 1.2, M* brightens by about 0.4–0.6 mag and φ* decreases by a factor 2–3. This trend persists, even if at a lesser extent, down to zm∼ 3 in both the Js- and Ks-band LF. The decline of the number density of bright galaxies seen at z > 0.8 suggests that a significant fraction of them increase their stellar mass at 1 < z < 2–3 and that they underwent a strong evolution in this redshift range. On the other hand, this implies also that a significant fraction of local bright/massive galaxies were already in place at z > 3. Thus, our results suggest that the assembly of massive galaxies is spread over a large redshift range and that the increase of their stellar mass has been very efficient also at very high redshift at least for a fraction of them.