There is an ongoing discussion in the literature on whether human mitochondrial DNA (mtDNA) evolves neutrally. There have been previous claims for natural selection on human mtDNA based on an excess of non-synonymous mutations and higher evolutionary persistence of specific mitochondrial mutations in Arctic populations. However, these findings were not supported by the reanalysis of larger datasets. Using a geographical framework, we perform the first direct test of the relative extent to which climate and past demography have shaped the current spatial distribution of mtDNA sequences worldwide. We show that populations living in colder environments have lower mitochondrial diversity and that the genetic differentiation between pairs of populations correlates with difference in temperature. These associations were unique to mtDNA; we could not find a similar pattern in any other genetic marker. We were able to identify two correlated non-synonymous point mutations in the ND3 and ATP6 genes characterized by a clear association with temperature, which appear to be plausible targets of natural selection producing the association with climate. The same mutations have been previously shown to be associated with variation in mitochondrial pH and calcium dynamics. Our results indicate that natural selection mediated by climate has contributed to shape the current distribution of mtDNA sequences in humans.