We present the results of a new study of the K-band galaxy luminosity function (KLF) at redshifts z<3.75, based on a nested combination of the UltraVISTA, CANDELS and HUDF surveys. The large dynamic range in luminosity spanned by this new dataset (3-4 dex over the full redshift range) is sufficient to clearly demonstrate for the first time that the faint-end slope of the KLF at z>0.25 is relatively steep (-1.3<alpha<-1.5 for a single Schechter function), in good agreement with recent theoretical and phenomenological models. Moreover, based on our new dataset we find that a double Schechter function provides a significantly improved description of the KLF at z<2. At redshifts z>0.25 the evolution of the KLF is remarkably smooth, with little or no evolution evident at faint (M_K>-20.5) or bright magnitudes (M_K<-24.5). Instead, the KLF is seen to evolve rapidly at intermediate magnitudes, with the number density of galaxies at M_K~-23 dropping by a factor of ~5 over the redshift interval 0.25<z<3.75. Motivated by this, we explore a simple description of the evolving KLF based on a double Schechter function with fixed faint-end slopes (alpha_1=-0.5, alpha_2=-1.5) and a shared characteristic magnitude (M_K*). According to this parameterisation, the normalisation of the component which dominates the faint-end of the KLF remains approximately constant, with phi*_2 decreasing by only a factor of ~2 between z~0 and z~3.25. In contrast, the component which dominates the bright end of the KLF at low redshifts evolves dramatically, becoming essentially negligible by z~3. Finally, we note that within this parameterisation, the observed evolution of M_K* between z~0 and z~3.25 is entirely consistent with M_K* corresponding to a constant stellar mass of M*~5x10^10 Msun at all redshifts.