We present a deep multicolor (U, B, V, I, Js, H, Ks) catalog of galaxies in the Hubble Deep Field South, based on observations obtained with the HST WFPC2 in 1998 and VLT-ISAAC in 1999. The photometric procedures were tuned to derive a catalog optimized for the estimation of photometric redshifts. In particular we adopted a "conservative" detection threshold, which resulted in a list of 1611 objects. The behavior of the observed source counts is in general agreement with the previous results of Casertano et al. in the Hubble Deep Field South and Williams et al. in the Hubble Deep Field North, while the corresponding counts in the Hubble Deep Field North provided by Fernández-Soto, Lanzetta, & Yahil are systematically lower by a factor 1.5 beyond IAB = 26. After correcting for the incompleteness of the source counts, the object surface density at IAB ≤ 27.5 is estimated to be 220 arcmin-2, in agreement with the corresponding measure of Volonteri et al. and providing an estimate of the extragalactic background light in the I band consistent with the work of Madau & Pozzetti. The comparison between the median V-I color in the Hubble Deep Field North and South shows a significant difference around IAB ~ 26, possibly due to the presence of large-scale structure at z ~ 1 in the HDF-N. High-redshift galaxy candidates (90 U dropouts and 17 B dropouts) were selected by means of color diagrams, down to a magnitude IAB = 27, with a surface density of (21 ± 1) and (3.9 ± 0.9) arcmin-2, respectively. Eleven extremely red objects [with (I-K)AB > 2.7] were selected down to KAB = 24, plus three objects whose upper limit to the Ks flux is still compatible with the selection criterion. The corresponding surface density of EROs is (2.5 ± 0.8) arcmin-2 [(3.2 ± 0.9) arcmin-2 if we include the three Ks upper limits]. They show a remarkably nonuniform spatial distribution and are classified with roughly equal fractions in the categories of elliptical and starburst galaxies.