The relativistic proton-neutron quasiparticle random phase approximation (PN-RQRPA) is applied in the calculation of total muon capture rates on a large set of nuclei from $^{12}$C to $^{244}$Pu, for which experimental values are available. The microscopic theoretical framework is based on the Relativistic Hartree-Bogoliubov (RHB) model for the nuclear ground state, and transitions to excited states are calculated using the PN-RQRPA. The calculation is fully consistent, i.e., the same interactions are used both in the RHB equations that determine the quasiparticle basis, and in the matrix equations of the PN-RQRPA. The calculated capture rates are sensitive to the in-medium quenching of the axial-vector coupling constant. By reducing this constant from its free-nucleon value $g_A = 1.262$ by 10% for all multipole transitions, the calculation reproduces the experimental muon capture rates to better than 10% accuracy.