There has been much recent work dedicated to exploring secondary correlations in the mass-metallicity relation, with significant dependence on both the star formation rate and HI content being demonstrated. Previously, a paucity of molecular gas data (combined with sample selection bias) hampered the investigation of any such relation with molecular gas content. In this work, we assemble a sample of 221 galaxies from a variety of surveys in the redshift range 0 < z < 2, to explore the connection between molecular gas content and metallicity. We explore the effect of gas mass on the mass-metallicity relation, finding that the offset from the relation is negatively correlated against both molecular and total gas mass. We then employ a principle component analysis technique to explore secondary dependences in the mass-metallicity relation, finding that the secondary dependence with gas mass is significantly stronger than with star formation rate, and as such the underlying `Fundamental Metallicity Relation' is between stellar mass, metallicity, and gas mass. In particular, the metallicity dependence on SFR is simply a byproduct of the dependence on the molecular gas content, via the Schmidt-Kennicutt relation. Finally, we note that our principle component analysis finds essentially no connection between gas-phase metallicity and the efficiency of star formation.