We have obtained ultradeep Js, H and Ks near-infrared imaging of the Hubble Deep Field South WFPC2 field with the ISAAC camera on the VLT. The total integration time of 100 hours resulted in the deepest ground-based infrared observations to date and the deepest Ks-band data ever taken. This depth allows us to determine the spectral energy distributions of the high-redshift galaxies with unprecendented accuracy. Together with existing optical observations, we use the multicolor data to select high-redshift galaxies by their rest-frame optical light, and study their statistical properties and morphologies. We find a wide variety of morphologies: some are large in the rest-frame optical and resemble normal spiral galaxies, others are barely detected in the observers optical and have red NIR colors. The latter belong to a new population of galaxies at redshifts z>2, that is notably absent in the HDF-North. The spectral energy distributions of many of such red galaxies show distinct breaks, which we identify as the balmer break/4000 Angstrom break, and their contribution to the stellar mass density is estimated to be substantial. At redshift z~3, we find a clear excess of superluminious galaxies (> 5 L*B(z=0)), which is consistent with 1 magnitude of luminosity evolution. Overall, the results show the necessity of deep near-infrared imaging to obtain a full census of the high redshift universe.