Magnetostriction drives a rhombohedral distortion in the cubic rock salt antiferromagnet MnO at the Nèel temperature TN=118 K. As an unexpected consequence we show that this distortion acts to localize the site of an implanted muon due to the accompanying redistribution of electron density. This lifts the degeneracy between equivalent sites, resulting in a single observed muon precession frequency. Above TN, the muon instead becomes delocalized around a network of equivalent sites. Our first-principles simulations based on Hubbard-corrected density-functional theory and molecular dynamics are consistent with our experimental data and help to resolve a long-standing puzzle regarding muon data on MnO, as well as having wider applicability to other magnetic oxides.