We report on low-resolution multi-object spectroscopy of 65 objects from I(AB) ~= 20 to I(AB) ~= 25 in the HDF-S obtained with the VLT Focal Reducer/low dispersion Spectrograph (FORS2). 18 objects belong to the HDF-S proper, i.e. the WFPC2 deep area. 15 high-redshift galaxies with 2.0 < z < 3.5 (10 in the HDF-S proper) have been identified. The spectroscopic redshifts are in good agreement with the photometric ones derived from a chi^{2} minimization technique comparing the observed spectral energy distribution with synthetic libraries and with a new neural network (NN) approach. The dispersion with the former method is sigma_z=0.16 whereas the latter provides sigma_z=0.13. No "catastrophic" difference is encountered. The inferred star formation rates of the individual objects range from tens to a few hundreds of M_{⊙} yr^{-1} and the global star formation rate of the Universe at =~2.4 is estimated to be 0.15 M_{⊙} yr^{-1} Mpc^{-3} with a statistical error of 0.04. Evidence for large scale structure is found with two groups' redshifts observed at z ~= 2.1 and z ~= 2.7 and a pronounced low redshift peak around z ~= 0.58. An elliptical galaxy lensing a background object turns out to be at a redshift z=0.577. Comment: 11 pages, 9 figures, Accepted for publication in A&A