  Heavy neutral leptons $N$ are the most appealing candidates to generate the
tiny neutrino masses. In this paper, we study the signature of heavy neutral
leptons in gauged $U(1)_{L_\mu-L_\tau}$ at a muon collider. Charged under the
$U(1)_{L_\mu-L_\tau}$ symmetry, the heavy neutral leptons can be pair produced
via the new gauge boson $Z'$ at muon collider as $\mu^+\mu^-\to Z^{\prime *}\to
NN$ and $\mu^+\mu^-\to Z^{\prime (*)} \gamma\to NN\gamma$. We then perform a
detailed analysis on the lepton number violation signature $\mu^+\mu^-\to NN\to
\mu^\pm\mu^\pm W^\mp W^\mp$ and $\mu^+\mu^-\to NN \gamma\to \mu^\pm\mu^\pm
W^\mp W^\mp \gamma$ at the 3 TeV muon collider, where the hadronic decays of
$W$ boson are treated as fat-jets $J$. These lepton number violation signatures
have quite clean backgrounds at the muon collider. Our simulation shows that a
wide range of viable parameter space is within the reach of the 3 TeV muon
collider. For instance, with new gauge coupling $g'=0.6$ and an integrated
luminosity of 1000 fb$^{-1}$, the $\mu^\pm\mu^\pm JJ$ signal could probe
$m_{Z'}\lesssim 12.5$ TeV. Meanwhile, if the gauge boson mass satisfies $2
m_N<m_{Z'}<\sqrt{s}$, the $\mu^\pm\mu^\pm JJ\gamma$ signature would be more
promising than the $\mu^\pm\mu^\pm JJ$ signature.
