Benthic foraminifera are unicellular eukaryotes that inhabit sediments of aquatic environments. Several foraminifera of the order Rotaliida are known to store and use nitrate for denitrification, a unique energy metabolism among eukaryotes. The rotaliid Globobulimina spp. has been shown to encode an incomplete denitrification pathway of bacterial origin. However, the prevalence of denitrification genes in foraminifera remains unknown, and the missing denitrification pathway components are elusive. Analyzing transcriptomes and metagenomes of 10 foraminiferal species from the Peruvian oxygen minimum zone, we show that denitrification genes are highly conserved in foraminifera. We infer the last common ancestor of denitrifying foraminifera, which enables us to predict the ability to denitrify for additional foraminiferal species. Additionally, an examination of the foraminiferal microbiota reveals evidence for a stable interaction with Desulfobacteraceae, which harbor genes that complement the foraminiferal denitrification pathway. Our results provide evidence that foraminiferal denitrification is complemented by the foraminifera-associated microbiome. The interaction of foraminifera with their resident bacteria is at the basis of foraminiferal adaptation to anaerobic environments that manifested in ecological success in oxygen depleted habitats.