We present the first results from the F aint I nfra- R ed E xtragalactic S urvey ( FIRES ) of the Hubble Deep Field ( HDF ) South . Using a combination of deep near infrared ( NIR ) data obtained with ISAAC at the VLT with the WFPC2 Hubble Space Telescope data , we construct a K-band selected sample which is 50 \% and 90 \% complete for K _ { s,AB } \leq 23.5 and K _ { s,AB } \leq 22.0 respectively where the magnitudes are measured over a 2 \farcs 0 diameter aperture . For z \leq 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 which is less dependent on their current star formation rate ( SFR ) than selection in the rest-frame UV . We developed a new photometric redshift technique which 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 HDF-N from the Cohen et al . ( 2000 ) sample and find \Delta z / ( 1 + z ) \approx 0.07 for z < 6 . We show that we can derive realistic error estimates in z _ { phot } by combining the systematic uncertainties derived from the HDF-N with errors in z _ { phot } 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 \mu m spectral energy distribution . In finding the correct z _ { phot } , 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 \approx 0.5 and a broad enhancement at z \sim 1 - 1.4 . We find that 12 \% of our galaxies with K _ { s,vega } < 21 lie at z \geq 2 . While this is higher than the fraction predicted in \Omega _ { 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 { L ^ { rest } } for z \leq 3 . There is a paucity of galaxies brighter than { L _ { V } ^ { rest } } \geq 1.4 \times 10 ^ { 10 } h ^ { -2 } L _ { \odot } at z \sim 1.5 - 2 , similar to what Dickinson ( 2001b ) found for the HDF-N . However , z _ { phot } 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 _ { V } ^ { rest } } \geq 5 \times 10 ^ { 10 } ~ { } h ^ { -2 } L _ { \odot } ( for \Omega _ { \mathrm { M } } = 0.3 ,~ { } \Omega _ { \Lambda } = 0.7 ,~ { } \mathrm { and~ { } H _ { o } } = 100 ~ { } % h~ { } km~ { } s ^ { -1 } Mpc ^ { -1 } ) . Local B-band luminosity functions predict 0.1 galaxies in the redshift range 2 \leq z \leq 3.5 and with { L _ { B } ^ { rest } } \geq 5 \times 10 ^ { 10 } ~ { } h ^ { -2 } L _ { \odot,B } but we find 9 . The discrepancy can be explained if { L } ^ { * } _ { B } 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 are required .