We present very deep near-infrared imaging in the Js, H and Ks-bands of the HDF-S and the field around the z=0.83 cluster MS1054-03 with ISAAC on the VLT. For the HDF-S this resulted in the deepest ground-based infrared observations to date and the deepest Ks-band in any field. We constructed Ks-selected multicolor catalogs in both fields, selecting high-redshift galaxies on their rest-frame optical light. We discovered a new, substantial population of optically faint galaxies with very red near-infrared colors (Js - Ks > 2.3) which are underrepresented in standard U-dropout samples. Recently, these galaxies were spectroscopically confirmed at redshifts z>2 and we estimate that they may contribute as much as 50% to the total stellar mass density at z~3. Furthermore, the near-infrared data allow direct measurement of the evolution of the global rest-frame optical color, luminosity density, and stellar mass density from z=0 to z=3. We find that the average rest-frame optical color was monotonically bluer in the past and the universe had a ~10 times lower stellar mass density in bright galaxies at z~3. In general, our results demonstrate the necessity of deep near-infrared imaging for a more complete picture of the early universe.