We use VANDELS spectroscopic data overlapping with the ≃7 Ms Chandra Deep Field South survey to extend studies of high-mass X-ray binary systems (HMXBs) in 301 normal star-forming galaxies in the redshift range 3 < z < 5.5. Our analysis evaluates correlations between X-ray luminosities (LX), star formation rates (SFRs), and stellar metallicities (Z∗) to higher redshifts and over a wider range in galaxy properties than hitherto. Using a stacking analysis performed in bins of both redshift and SFR for sources with robust spectroscopic redshifts without AGN signatures, we find convincing evolutionary trends in the ratio LX/SFR to the highest redshifts probed, with a stronger trend for galaxies with lower SFRs. Combining our data with published samples at lower redshift, the evolution of LX/SFR to z ≃ 5 proceeds as (1 + z)1.03 ± 0.02. Using stellar metallicities derived from photospheric absorption features in our spectroscopic data, we confirm indications at lower redshifts that LX/SFR is stronger for metal-poor galaxies. We use semi-analytic models to show that metallicity dependence of LX/SFR alone may not be sufficient to fully explain the observed redshift evolution of X-ray emission from HMXBs, particularly for galaxies with SFR < 30 M⊙ yr-1. We speculate that reduced overall stellar ages and 'burstier' star formation histories in the early Universe may lead to higher LX/SFR for the same metallicity. We then define the redshift-dependent contribution of HMXBs to the integrated X-ray luminosity density and, in comparison with models, find that the contribution of HMXBs to the cosmic X-ray background at z > 6 may be ≳0.25 dex higher than previously estimated.