We present the rest-frame V-band luminosity function (LF) of galaxies at 0.4<z<4.0, measured from a near-infrared selected sample constructed from the NMBS, the FIRES, the FIREWORKS, and the ultra-deep NICMOS and WFC3 observations in the HDFN, HUDF, and GOODS-CDFS, all having high-quality optical to mid-infrared data. This unique sample combines data from surveys with a large range of depths and areas in a self-consistent way, allowing us to (1) minimize the uncertainties due to cosmic variance; and (2) simultaneously constrain the bright and faint ends with unprecedented accuracy over the targeted redshift range, probing the LF down to 0.1 L* at z~3.9. We find that (1) the faint end is fairly flat and with a constant slope from z=4, with alpha= -1.27 +/- 0.05; (2) the characteristic magnitude has dimmed by 1.3 mag from z~3.7 to z=0.1; (3) the characteristic density has increased by a factor of ~8 from z~3.7 to z=0.1, with 50% of this increase from z~4 to z~1.8; and (4) the luminosity density peaks at z~1-1.5, increasing by a factor of ~4 from z=4.0 to z~1-1.5, and subsequently decreasing by a factor of ~1.5 by z=0.1. We find no evidence for a steepening of the faint-end slope with redshift out to z=4, in contrast with previous observational claims and theoretical predictions. The constant faint-end slope suggests that the efficiency of stellar feedback may evolve with redshift. Alternative interpretations are discussed, such as different masses of the halos hosting faint galaxies at low and high redshifts and/or environmental effects.