We present deep near-infrared (NIR) Js, H, and Ks-band ISAAC imaging of the WFPC2 field of the HDF-S. The 2.5x 2.5 high Galactic latitude field was observed with the VLT under the best seeing conditions with integration times amounting to 33.6 hours in Js, 32.3 hours in H, and 35.6 hours in Ks. We reach total AB magnitudes for point sources of 26.8, 26.2, and 26.2 respectively (3 sigma), which make it the deepest ground-based NIR observations to date, and the deepest Ks-band data in any field. The effective seeing of the coadded images is ~0.45 in Js, ~0.48 in H, and ~0.46 in Ks. Using published WFPC2 optical data, we constructed a Ks-limited multicolor catalog containing 833 sources down to Ks,tot ~< 26 (AB), of which 624 have seven-band optical-to-NIR photometry. These data allow us to select normal galaxies from their rest-frame optical properties to high redshift (z ~< 4). The observations, data reduction and properties of the final images are discussed, and we address the detection and photometry procedures that were used in making the catalog. In addition, we present deep number counts, color distributions and photometric redshifts of the HDF-S galaxies. We find that our faint Ks-band number counts are flatter than published counts in other deep fields, which might reflect cosmic variations or different analysis techniques. Compared to the HDF-N, we find many galaxies with very red V-H colors at photometric redshifts 1.95 < z < 3.5. These galaxies are bright in Ks with infrared colors redder than Js-Ks > 2.3 (in Johnson magnitudes). Because they are extremely faint in the observed optical, they would be missed by ultraviolet-optical selection techniques, such as the U-dropout method.