We use cosmological hydrodynamic simulations with enriched galactic outflows to compare predictions for the galaxy mass-metallicity (M* − Z) with observations at z ≈ 2 from Erb et al. (2006). With no outflows included 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 in 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 heyday of star formation in the Universe.