Context. Infrared-faint radio sources (IFRS) are characterised by relatively high radio flux densities and associated faint or even absent infrared and optical counterparts. The resulting extremely high radio-to-infrared flux density ratios up to several thousands were previously known only for high-redshift radio galaxies (HzRGs), suggesting a link between the two classes of object. However, the optical and infrared faintness of IFRS makes their study difficult. Prior to this work, no redshift was known for any IFRS in the Australia Telescope Large Area Survey (ATLAS) fields which would help to put IFRS in the context of other classes of object, especially of HzRGs. Aims. This work aims at measuring the first redshifts of IFRS in the ATLAS fields. Furthermore, we test the hypothesis that IFRS are similar to HzRGs, that they are higher-redshift or dust-obscured versions of these massive galaxies. Methods. A sample of IFRS was spectroscopically observed using the Focal Reducer and Low Dispersion Spectrograph 2 (FORS2) at the Very Large Telescope (VLT). The data were calibrated based on the Image Reduction and Analysis Facility (IRAF) and redshifts extracted from the final spectra, where possible. This information was then used to calculate rest-frame luminosities, and to perform the first spectral energy distribution modelling of IFRS based on redshifts. Results. We found redshifts of 1.84, 2.13, and 2.76, for three IFRS, confirming the suggested high-redshift character of this class of object. These redshifts and the resulting luminosities show IFRS to be similar to HzRGs, supporting our hypothesis. We found further evidence that fainter IFRS are at even higher redshifts. Conclusions. Considering the similarities between IFRS and HzRGs substantiated in this work, the detection of IFRS, which have a significantly higher sky density than HzRGs, increases the number of active galactic nuclei in the early universe and adds to the problems of explaining the formation of supermassive black holes shortly after the Big Bang.