We discuss a minimal solution to the long-standing $(g-2)_\mu$ anomaly in a simple extension of the Standard Model with an extra $Z'$ vector boson that has only flavor off-diagonal couplings to the second and third generation of leptons, i.e. $\mu, \tau, \nu_\mu, \nu_\tau$ and their antiparticles. A simplified model realization, as well as various collider and low-energy constraints on this model, are discussed. We find that the $(g-2)_\mu$-favored region for a $Z'$ lighter than the tau lepton is totally excluded, while a heavier $Z'$ solution is still allowed. Some testable implications of this scenario in future experiments, such as lepton-flavor universality-violating tau decays at Belle 2, and a new four-lepton signature involving same-sign di-muons and di-taus at HL-LHC and FCC-ee, are pointed out. A characteristic resonant absorption feature in the high-energy neutrino spectrum might also be observed by neutrino telescopes like IceCube and KM3NeT.