Cell-to-cell heterogeneity drives a range of (patho)physiologically important phenomena, such as cell fate and chemotherapeutic resistance. The role of metabolism, and particularly of mitochondria, is increasingly being recognized as an important explanatory factor in cell-to-cell heterogeneity. Most eukaryotic cells possess a population of mitochondria, in the sense that mitochondrial DNA (mtDNA) is held in multiple copies per cell, where the sequence of each molecule can vary. Hence, intra-cellular mitochondrial heterogeneity is possible, which can induce inter-cellular mitochondrial heterogeneity, and may drive aspects of cellular noise. In this review, we discuss sources of mitochondrial heterogeneity (variations between mitochondria in the same cell, and mitochondrial variations between supposedly identical cells) from both genetic and non-genetic perspectives, and mitochondrial genotype-phenotype links. We discuss the apparent homeostasis of mtDNA copy number, the observation of pervasive intra-cellular mtDNA mutation (which is termed “microheteroplasmy”), and developments in the understanding of inter-cellular mtDNA mutation (“macroheteroplasmy”). We point to the relationship between mitochondrial supercomplexes, cristal structure, pH, and cardiolipin as a potential amplifier of the mitochondrial genotype-phenotype link. We also discuss mitochondrial membrane potential and networks as sources of mitochondrial heterogeneity, and their influence upon the mitochondrial genome. Finally, we revisit the idea of mitochondrial complementation as a means of dampening mitochondrial genotype-phenotype links in light of recent experimental developments. The diverse sources of mitochondrial heterogeneity, as well as their increasingly recognized role in contributing to cellular heterogeneity, highlights the need for future single-cell mitochondrial measurements in the context of cellular noise studies.