CO measurements of z~1-4 galaxies have found that their baryonic gas fractions are significantly higher than galaxies at z=0, with values ranging from 20-80 %. Here, we suggest that the gas fractions inferred from observations of star-forming galaxies at high-z are overestimated, owing to the adoption of locally-calibrated CO-H2 conversion factors (Xco). Evidence from both observations and numerical models suggest that Xco varies smoothly with the physical properties of galaxies, and that Xco can be parameterised simply as a function of both gas phase metallicity and observed CO surface brightness. When applying this functional form, we find fgas ~10-40 % in galaxies with M*=10^10-10^12 Msun at high-z. Moreover, the scatter in the observed fgas-M* relation is lowered by a factor of two. The lower inferred gas fractions arise physically because the interstellar media of high-z galaxies have higher velocity dispersions and gas temperatures than their local counterparts, which results in an Xco that is lower than the z=0 value for both quiescent discs and starbursts. We further compare these gas fractions to those predicted by cosmological galaxy formation models. We show that while the canonically inferred gas fractions from observations are a factor of 2-3 larger at a given stellar mass than predicted by models, our rederived Xco values for z=1-4 galaxies results in revised gas fractions that agree significantly better with the simulations.