The mammalian mitochondrial genomes differ from the nuclear genomes by maternal inheritance, absence of recombination, and higher mutation rate. All these differences decrease the effective population size of mitochondrial genome and make it more susceptible to accumulation of slightly deleterious mutations. It was hypothesized that mitochondrial genes, especially in species with low effective population size, irreversibly degrade leading to decrease of organismal fitness and even to extinction of species through the mutational meltdown. To interrogate this hypothesis, we compared the purifying selections acting on the representative set of mitochondrial (potentially degrading) and nuclear (potentially not degrading) protein-coding genes in species with different effective population size. For 21 mammalian species, we calculated the ratios of accumulation of slightly deleterious mutations approximated by Kn/Ks separately for mitochondrial and nuclear genomes. The 75% of variation in Kn/Ks is explained by two independent variables: type of a genome (mitochondrial or nuclear) and effective population size of species approximated by generation time. First, we observed that purifying selection is more effective in mitochondria than in the nucleus that implies strong evolutionary constraints of mitochondrial genome. Mitochondrial de novo nonsynonymous mutations have at least 5-fold more harmful effect when compared with nuclear. Second, Kn/Ks of mitochondrial and nuclear genomes is positively correlated with generation time of species, indicating relaxation of purifying selection with decrease of species-specific effective population size. Most importantly, the linear regression lines of mitochondrial and nuclear Kn/Ks's from generation times of species are parallel, indicating congruent relaxation of purifying selection in both genomes. Thus, our results reveal that the distribution of selection coefficients of de novo nonsynonymous mitochondrial mutations has a similar shape with the distribution of de novo nonsynonymous nuclear mutations, but its mean is five times smaller. The harmful effect of mitochondrial de novo nonsynonymous mutations triggers highly effective purifying selection, which maintains the fitness of the mammalian mitochondrial genome.