We present the results of a study utilizing ultradeep, rest-frame UV, spectroscopy to quantify the relationship between stellar mass and stellar metallicity for 681 star-forming galaxies at 2.5 < z < 5.0 (⟨z⟩ = 3.5 ± 0.6) drawn from the VANDELS survey. Via a comparison with high-resolution stellar population synthesis models, we determine stellar metallicities (Z∗, here a proxy for the iron abundance) for a set of high signal-to-noise ratio composite spectra formed from subsamples selected by mass and redshift. Across the stellar mass range 8.5<log(⟨M∗⟩/M⊙)<10.2, we find a strong correlation between stellar metallicity (Z∗/Z⊙) and stellar mass, with stellar metallicity monotonically increasing from Z∗/Z⊙ < 0.09 at ⟨M∗⟩=3.2×108M⊙ to Z∗/Z⊙ = 0.27 at ⟨M∗⟩=1.7×1010M⊙. In contrast, at a given stellar mass, we find no evidence for significant metallicity evolution across the redshift range of our sample. However, comparing our results to the z = 0 stellar mass–metallicity relation for star-forming galaxies, we find that the ⟨z⟩ = 3.5 relation is consistent with being shifted to lower metallicities by ≃0.6 dex at all stellar masses. Contrasting our derived stellar metallicities with estimates of the gas-phase metallicities of galaxies at similar redshifts and stellar masses, we find evidence for enhanced O/Fe ratios in z ≳ 2.5 star-forming galaxies of the order (O/Fe) ≳ 1.8 × (O/Fe)⊙. Finally, by comparing our results to the predictions of three cosmological simulations, we find that the ⟨z⟩ = 3.5 stellar mass–metallicity relation is consistent with current predictions for how outflow strength scales with galaxy stellar mass. This conclusion is supported by an analysis of one-zone analytic chemical evolution models, and suggests that the mass-loading parameter (η=M˙outflow/M∗) scales as η∝Mβ∗ with β ≃ −0.4.