  We study the phenomenology of leptophilic $Z'$ gauge bosons at the future
high-energy $e^+e^-$ and $\mu^+\mu^-$ colliders, as well as at the
gravitational wave observatories. The leptophilic $Z'$ model, although
well-motivated, remains largely unconstrained from current low-energy and
collider searches for $Z'$ masses above ${\cal O}(100~{\rm GeV})$, thus
providing a unique opportunity for future lepton colliders. Taking
$U(1)_{L_\alpha-L_\beta}~(\alpha,\beta=e,\mu,\tau)$ models as concrete
examples, we show that future $e^+e^-$ and $\mu^+\mu^-$ colliders with
multi-TeV center-of-mass energies provide unprecedented sensitivity to heavy
leptophilic $Z'$ bosons. Moreover, if these $U(1)$ models are classically
scale-invariant, the phase transition at the $U(1)$ symmetry-breaking scale
tends to be strongly first-order with ultra-supercooling, and leads to
observable stochastic gravitational wave signatures. We find that the future
sensitivity of gravitational wave observatories, such as advanced LIGO-VIRGO
and Cosmic Explorer, can be complementary to the collider experiments, probing
higher $Z'$ masses up to ${\cal O}(10^4~{\rm TeV})$, while being consistent
with naturalness and perturbativity considerations.
