BACKGROUND Bifidobacteria are among the first anaerobic bacteria colonizing the gut. Bifidobacteria require iron for growth and their iron-sequestration mechanisms are important for their fitness and possibly inhibit enteropathogens. Here we used combined genomic and proteomic analyses to characterize adaptations to low iron conditions of B. kashiwanohense PV20-2 and B. pseudolongum PV8-2, 2 strains isolated from the feces of iron-deficient African infants and selected for their high iron-sequestering ability. RESULTS Analyses of the genome contents revealed evolutionary adaptation to low iron conditions. A ferric and a ferrous iron operon encoding binding proteins and transporters were found in both strains. Remarkably, the ferric iron operon of B. pseudolongum PV8-2 is not found in other B. pseudolongum strains and likely acquired via horizontal gene transfer. The genome B. kashiwanohense PV20-2 harbors a unique region encoding genes putatively involved in siderophore production. Additionally, the secretomes of the two strains grown under low-iron conditions were analyzed using a combined genomic-proteomic approach. A ferric iron transporter was found in the secretome of B. pseudolongum PV8-2, while ferrous binding proteins were detected in the secretome of B. kashiwanohense PV20-2, suggesting different strategies to take up iron in the strains. In addition, proteins such as elongation factors, a glyceraldehyde-3-phosphate dehydrogenase, and the stress proteins GroEL and DnaK were identified in both secretomes. These proteins have been previously associated with adhesion of lactobacilli to epithelial cells. CONCLUSION Analyses of the genome and secretome of B. kashiwanohense PV20-2 and B. pseudolongum PV8-2 revealed different adaptations to low iron conditions and identified extracellular proteins for iron transport. The identified extracellular proteins might be involved in competition for iron in the gastrointestinal tract.