We study the discovery potential of the non-Standard Model (SM) heavy Higgs bosons in the Two-Higgs-Doublet Models (2HDMs) at a multi-TeV muon collider and explore the discrimination power among different types of 2HDMs. We find that the pair production of the non-SM Higgs bosons via the universal gauge interactions is the dominant mechanism once above the kinematic threshold. Single Higgs boson production associated with a pair of heavy fermions could be important in the parameter region with enhanced Yukawa couplings. For both signal final states, $mu^+ mu^-$ annihilation channels dominate over the vector boson fusion (VBF) processes, except at high center of mass energies where the VBF processes receive large logarithmic enhancement with the increase of energies. Single Higgs boson $s$-channel production in $mu^+ mu^-$-annihilation via the radiative return can also be important for the Type-L 2HDM in the very large $tanbeta$ region, extending the kinematic reach of the heavy Higgs boson mass to the collider energy. Considering both the production and decay of non-SM Higgs bosons, signals can be identified over the Standard Model backgrounds. Different types of 2HDMs can be distinguishable for moderate and large values of $tanbeta$.