The redshift evolution of the Tully-Fisher Relation probes gravitational dynamics that must be consistent with any modified gravity theory seeking to explain the galactic rotation curves without the need for dark matter. Within the context of non-relativistic Modified Newtonian Dynamics (MOND), the characteristic acceleration scale of the theory appears to be related to the current value of either the Hubble constant, i.e., alpha ~ cH_0, or the dark energy density, i.e., alpha (8 pi G rho_lambda/3)^{1/2}. If these relations are the manifestation of a fundamental coupling of a_0 to either of the two cosmological parameters, the cosmological evolution would then dictate a particular dependence of the MOND acceleration scale with redshift that can be tested with Tully-Fisher relations of high-redshift galaxies. We compare this prediction to two sets of Tully-Fisher data with redshifts up to z=1.2. We find that both couplings are excluded within the formal uncertainties. However, when we take into account the potential systematic uncertainties in the data, we find that they marginally favor the coupling of the MOND acceleration scale to the density of dark energy.