Iron acquisition represents a particular challenge for pathogenic microorganisms, because of the iron withholding mechanisms deployed by the host. Many microbial pathogens, including fungi such as Candida albicans, have therefore evolved mechanisms for extracting iron from hemoglobin, the largest iron store in the host, by removing the heme cofactor from the globins, and transferring it to the microbe’s cytoplasm. Elucidation of this pathway in C. albicans by genetic means was however hampered by the fact that this organism is not suited for forward genetic screening, and that the pathway is absent from the model yeast S. cerevisiae. Screening of a C. albicans library introduced in yeast enabled the initial identification of a family of extracellular heme-binding proteins involved in heme-iron utilization. These proteins all include a CFEM sequence signature, consisting of 8 cysteines with conserved spacing. We solved the structure of the hemophore Csa2, revealing that the CFEM domain adopts a novel protein fold, held together by 4 disulfide bonds generated by the 8 conserved cysteines, and that it displays a unique heme-iron coordination mechanism. CFEM proteins involved in heme utilization are either secreted, or are GPI-anchored at different locations in the cell envelope. These proteins all are able to capture heme from hemoglobin and to transfer it between themselves, consistent with a pathway in which heme is extracted from hemoglobin outside the cell and is then transferred from one CFEM protein to the next until it reaches the plasma membrane - whereupon it is endocytosed by a mechanism previously shown to involve the ESCRT pathway. A missing link was the putative transmembrane heme receptor that connects the extracellular CFEM network with the endocytic pathway. To identify candidates for such a receptor, we resorted to phylogenetic profiling: taking advantage of the hundreds of fungal genomes available, we screened for genes jointly present with the CFEM heme transfer cascade genes across fungi. This enabled us to identify a new class of plasma membrane proteins that are essential for heme uptake. The hemoglobin-iron utilization pathway that emerges from these studies, which is distinct from bacterial systems, indicates that fungi have evolved a unique solution to the heme-iron acquisition problem. Phylogenetic profiling is shown here to represent a powerful method for unraveling cellular pathways in organisms that are recalcitrant to conventional genetic screening.