We use cosmological hydrodynamic simulations with enriched galactic outflows to compare predictions for the galaxy mass-metallicity (M*-Z) relation versus observations at z~2 from Erb et al. (2006). With no outflows, galaxies are over-enriched, indicating that outflows are required not only to suppress star formation and enrich the IGM but also to lower galaxy metal content. The observed M*-Z slope is matched both in our model without winds as well as our favored outflow model where the outflow velocity scales as the escape velocity, but is too steep in a model with constant outflow speeds. If outflows are too widespread at early times, the IGM out of which smaller galaxies form can become pre-polluted, resulting in a low-mass flattening of the M*-Z relation that is inconsistent with data. Remarkably, the same momentum-driven wind model that provides the best agreement with IGM enrichment data also yields the best agreement with the z~2 M*-Z relation, showing the proper outflow scaling and strength to match the observed slope and amplitude. In this model, the M*-Z relation evolves slowly from z=6-2; an (admittedly uncertain) extrapolation to z=0 broadly matches local M*-Z observations. Overall, the M*-Z relation provides critical constraints on galactic outflow processes during the heydey of star formation in the Universe.