We present the first results from the Faint Infra-Red Extragalactic Survey of the Hubble Deep Field South (HDF-S). Using a combination of deep near-infrared (NIR) data obtained with the Infrared Spectrograph and Array Camera at the VLT and the WFPC2 Hubble Space Telescope data, we construct a K-band–selected sample which is 50% and 90% complete for Ks,AB ≤ 23.5 and Ks,AB ≤ 22.0, respectively, where the magnitudes are measured over a 20 diameter aperture. For z ≤ 3, our selection by the K-band flux chooses galaxies based on wavelengths redder than the rest-frame V band, and so selects them in a way that is less dependent on their current star formation rates than selection in the rest-frame UV. We developed a new photometric redshift technique that models the observed spectral energy distribution (SED) with a linear combination of empirical galaxy templates. We tested this technique using 150 spectroscopic redshifts in the Hubble Deep Field North (HDF-N) from the Cohen et al. sample (published in 2000) and found Δz/(1 + z) ≈ 0.07 for z < 6. We show that we can derive realistic error estimates in zphot by combining the systematic uncertainties derived from the HDF-N with errors in zphot, which depend on the observed flux errors. We estimate photometric redshifts for 136 galaxies in the HDF-S from the full seven-band, 0.3–2.2 μm SED. In finding the correct zphot, our deep NIR data is important for breaking the redshift degeneracy between templates of identical observed optical colors. The redshift histogram of galaxies in the HDF-S shows distinct structure with a sharp peak at z ≈ 0.5 and a broad enhancement at z ~ 1–1.4. We find that 12% of our galaxies with Ks,vega < 21 lie at z ≥ 2. While this is higher than the fraction predicted in ΩM = 1 hierarchical models of galaxy formation, we find that published predictions using pure luminosity evolution models produce too many bright galaxies at redshifts greater than unity. Finally, we use our broad wavelength coverage to measure the rest-frame UBV luminosities, Lrest, for z ≤ 3. There is a paucity of galaxies brighter than L ≥ 1.4 × 1010 h-2 L at z ~ 1.5–2, similar to what Dickinson found for the HDF-N (published in 2001). However, zphot is particularly uncertain in this regime, and spectroscopic confirmation is required. We also note that at z > 2 we find very luminous galaxies with L ≥ 5 × 1010 h-2 L (for ΩM = 0.3, ΩΛ = 0.7, and H0 = 100 h km s-1 Mpc-1). Local B-band luminosity functions predict 0.1 galaxies in the redshift range 2 ≤ z ≤ 3.5 and with L ≥ 5 × 1010 h-2 L,B, but we find nine. The discrepancy can be explained if L increases by a factor of 2.4–3.2 with respect to locally determined values. Random errors in the photometric redshift can also play a role, and spectroscopic confirmation of the redshifts of these bright galaxies is required.