Our current understanding of paleoecology and paleoceanography is largely based on the superb Phanerozoic fossil record of foraminiferan protists. The early history of the group is unresolved, however, because basal foraminiferans (allogromiids) are unmineralized and thus fossilize poorly. Molecular-clock studies date foraminiferal origins to the Neoproterozoic, but the deep sea, one of Earth's most extensive habitats and presently hosting a significant fraction of basal foraminiferal diversity, was probably anoxic at that time and, until now, anaerobic allogromiids were unknown. Molecular, cell, and ecological analyses reveal the presence of a previously unknown allogromiid inhabiting anoxic, sulfidic deep-sea sediments (Santa Barbara Basin, California). The fact that the new foraminifer harbors prokaryotic endobionts implicates symbiogenesis as a driving force in early foraminiferal diversification.