Abridged We present the rest-frame Js-band and Ks-band luminosity function of a sample of about 300 galaxies selected in the HDF-S at Ks<23 (Vega). We use calibrated photometric redshift together with spectroscopic redshift for 25% of the sample. The sample has allowed to probe the evolution of the LF in the three redshift bins 0;0.8), 0.8;1.9) and 1.9;4) centered at the median redshift z_m ~ 0.6,1.2,3. The values of alpha 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 z_m ~ 0.6 suggesting that the population of local bright galaxies was already formed at z<0.8. On the contrary, we clearly detect an evolution of the LF to z_m ~ 1.2 characterized by a brightening of M* and by a decline of phi*. To z_m ~ 1.2 M* brightens by about 0.4-0.6 mag and phi* decreases by a factor 2-3. This trend persists, even if at a less extent, down to z_m ~ 3 both in the Js-band and in the Ks-band LF. The decline of the number density of bright galaxies seen at z>0.8 suggests that a significant fraction of them increases 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 was already in place at z>3. Thus, our results suggest that the assembly of high-mass 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.