Recent results have suggested that the well known mass-metallicity relation has a strong dependence on the star formation rate, to the extent that a three dimensional `fundamental metallicity relation' exists which links the three parameters with minimal scatter. In this work, we use a sample of 4253 local galaxies observed in atomic hydrogen from the ALFALFA survey to demonstrate, for the first time, that a similar fundamental relation (the HI-FMR) also exists between stellar mass, gas-phase metallicity, and HI mass. This latter relation is likely more fundamental, driving the relation between metallicity, SFR and mass. At intermediate masses, the behaviour of the gas fundamental metallicity relation is very similar to that expressed via the star formation rate. However, we find that the dependence of metallicity on HI content persists to the highest stellar masses, in contrast to the `saturation' of metallicity with SFR. It is interesting to note that the dispersion of the relation is very low at intermediate stellar masses (9< log(M*/Msun) <11), suggesting that in this range galaxies evolve smoothy, in an equilibrium between gas inflow, outflow and star formation. At high and low stellar masses, the scatter of the relation is significantly higher, suggesting that merging events and/or stochastic accretion and star formation may drive galaxies outside the relation. We also assemble a sample of galaxies observed in CO. However, due to a small sample size, strong selection bias, and the influence of a metallicity-dependent CO/H2 conversion factor, the data are insufficient to test any influence of molecular gas on metallicity.