Theories of gravity that incorporate new scalar degrees of freedom typically require screening mechanisms to ensure consistency with Solar System tests. One widely-studied mechanism -- the chameleon -- can lead to violations of the equivalence principle (EP), as screened and unscreened objects fall differently. If the stars are screened but the surrounding dark matter is not, this leads to asymmetry between leading and trailing streams. We provide analytic estimates of the magnitude of this effect for realistic Galactic mass distributions. Using a restricted N-body code, we simulate 4 satellites with a range of masses and orbits, together with a variety of strengths of the fifth force and screening levels of the Milky Way and satellite. The ratio of the cumulative number function of stars in the leading and trailing stream as a function of longitude from the satellite is computable from simulations, measurable from the stellar data and can provide a direct test. We forecast constraints for streams at large Galactocentric distances, using the specific example case of Hu-Sawicki gravity. Streams with apocentres between 100 and 200 kpc provide attainable constraints at the level of $|f_{R0}| = 10^{-7}$. Still more stringent constraints at the level of $10^{-7.5}$ or even $10^{-8}$ are plausible provided the environmental screening of the satellite is accounted for. These would be among the tightest astrophysical constraints to date. We note further signatures of chameleon gravity: (i) the trailing stellar stream may become detached from the dark matter progenitor if all the stars are lost, (ii) in the extreme fifth force regime, striations in the stellar trailing tail may develop, (iii) if the satellite is fully screened, its orbital frequency is lower than that of the associated dark matter, which is preferentially liberated into the leading tidal tail.

PRD, 22 pages, 14 figures