The clustering properties of faint K-Vega < 24 galaxies are measured in ultradeep J, H, and K near-IR images of the Hubble Deep Field-South (HDF-S), obtained with ISAAC at the Very Large Telescope. As a function of the K magnitude, a relatively large clustering amplitude is found up to K = 24, at a level comparable to the measurements at K similar to 19. The photometric redshift distribution of K < 24 galaxies extends to z(phot) similar to4-5, and similar to40% of the galaxies are at z(phot) > 2. At the highest redshifts, 2 < z(phot) < 4, galaxies selected in the rest-frame optical ( K band) appear significantly more clustered than galaxy populations selected in the rest-frame UV (i.e., Lyman break galaxies [LBGs]), in a similar redshift range and with similar number densities. Galaxy clustering depends on the J-K color at 2 < z(phot) < 4, with the K-selected galaxies with J-K > 1: 7 reaching r(0) similar to8 h(-1) Mpc comoving. This is a factor of 3-4 higher than the correlation length of LBGs with similar number densities, down to V-606 < 27, and is also larger than the correlation length of K-selected galaxies with blue J-K < 1.7 colors. Hence, at z approximate to 3 a color-density relation is observed that is qualitatively similar to that observed locally. Fluctuations in the amplitude of clustering due to cosmic variance may affect our estimates derived from the small HDF-S field, but these are unlikely to change our main conclusions. The galaxies with red J-K > 1.7 colors at 2 < z(phot) < 4 are likely older and more massive galaxies, on average, than LBGs. They were presumably formed in the highest density perturbations at early epochs. Semianalytical hierarchical models do predict the existence of strongly clustered populations at z similar to 3 but with at least a factor of 10 lower number density than the one measured. The overall properties of this strongly clustered population consistently suggest that they are the progenitors, or building blocks, of local massive early-type galaxies and z similar to 1 extremely red objects, close to their major epochs of formation.