We present the most accurate measurement to date of cosmological evolution of the near-infrared galaxy luminosity function, from the local Universe out to z~4. The analysis is based on a large and highly complete sample of galaxies selected from the first data release of the UKIDSS Ultra Deep Survey. Exploiting a master catalogue of K- and z-band selected galaxies over an area of 0.7 square degrees, we analyse a sample of ~50,000 galaxies, all with reliable photometry in 16-bands from the far-ultraviolet to the mid-infrared. The unique combination of large area and depth provided by the Ultra Deep Survey allows us to trace the evolution of the K-band luminosity function with unprecedented accuracy. In particular, via a maximum likelihood analysis we obtain a simple parameterization for the luminosity function and its cosmological evolution, including both luminosity and density evolution, which provides an excellent description of the data from z =0 up to z~4. We find differential evolution for galaxies dependent on galaxy luminosity, revealing once again the ``down-sizing behaviour of galaxy formation. Finally, we compare our results with the predictions of the latest theoretical models of galaxy formation, based both on semi-analytical prescriptions, and on full hydrodynamical simulations.