Heme biosynthesis consists of a series of eight enzymatic reactions that originate in mitochondria and continue in the cytosol before returning to mitochondria. Although these core enzymes are well studied, additional mitochondrial transporters and regulatory factors are predicted to be required. To discover such unknown components, we utilized a large-scale computational screen to identify mitochondrial proteins whose transcripts consistently coexpress with the core machinery of heme biosynthesis. We identified SLC25A39, SLC22A4, and TMEM14C, which are putative mitochondrial transporters, as well as C1orf69 and ISCA1, which are iron-sulfur cluster proteins. Targeted knockdowns of all five genes in zebrafish resulted in profound anemia without impacting erythroid lineage specification. Moreover, silencing of Slc25a39 in murine erythroleukemia cells impaired iron incorporation into protoporphyrin IX, and vertebrate Slc25a39 complemented an iron homeostasis defect in the orthologous yeast mtm1Δ deletion mutant. Our results advance the molecular understanding of heme biosynthesis and offer promising candidate genes for inherited anemias.