The mitochondrial histone HM is the major DNA-binding protein in mitochondria and is necessary for maintenance of the mitochondrial genome in the yeast Saccharomyces cerevisiae during growth on fermentable sugars. HM and the Escherichia coli histone-like protein HU have similar activities in vitro, including DNA supercoiling, but share no sequence similarity. We show that HU can functionally complement the respiration deficiency associated with yeast strains lacking HM. Conversely, phenotypes of E. coli cells lacking HU protein, including nucleoid loss and a filamentous cell morphology, were alleviated by expression of HM in these cells. The HU protein of bacteria and the HM protein of mitochondria are therefore functionally complementary in vivo. Functional similarities among HM, HU, and the nuclear HMG1 proteins are implicated and discussed.