We present reliable measurements of the metallicity distribution function (MDF) at different points along the tidal stream of the Sagittarius (Sgr) dwarf spheroidal (dSph) galaxy, based on high-resolution, echelle spectroscopy of candidate M giant members of the Sgr system. The Sgr MDF is found to evolve significantly from a median [Fe/H]~-0.4 in the core to ~-1.1 dex over a Sgr leading arm length representing ~2.5-3.0 Gyr of dynamical (i.e., tidal stripping) age. This is direct evidence that there can be significant chemical differences between current dSph satellites and the bulk of the stars they have contributed to the halo. Our results suggest that Sgr experienced a significant change in binding energy over the past several gigayears, which has substantially decreased its tidal boundary across a radial range over which there must have been a significant metallicity gradient in the progenitor galaxy. By accounting for MDF variation along the debris arms, we approximate the MDF Sgr would have had several gigayears ago. We also analyze the MDF of a moving group of M giants we previously discovered toward the north Galactic cap. These objects have the opposite radial velocities to the infalling Sgr leading arm stars there, and we propose that most of them represent Sgr trailing arm stars overlapping the Sgr leading arm in this part of the sky. If so, these trailing arm stars further demonstrate the strong MDF evolution within the Sgr stream.