Present knowledge of microbial diversity is decidedly incomplete (S. J. Giovannoni and M. S. Rappé, p. 47-84, in D. Kirchman, ed., Microbial Ecology of the Oceans, 2000; E. Stackebrandt and T. M. Embley, p. 57-75, in R. R. Colwell and D. J. Grimes, ed., Nonculturable Microorganisms in the Environment, 2000). Protistan phylogenies are particularly deficient and undoubtedly exclude clades of principal ecological and evolutionary importance (S. L. Baldauf, Science 300:1703-1706, 2003). The rRNA approach has been extraordinarily successful in expanding the global prokaryotic record (S. J. Giovannoni and M. S. Rappé, p. 47-84, in D. Kirchman, ed., Microbial Ecology of the Oceans, 2000; E. Stackebrandt and T. M. Embley, p. 57-75, in R. R. Colwell and D. J. Grimes, ed., Nonculturable Microorganisms in the Environment, 2000) but has rarely been used in protistan discovery. Here we report the first application of the 18S rRNA approach to a permanently anoxic environment, the Cariaco Basin off the Venezuelan coast. On the basis of rRNA sequences, we uncovered a substantial number of novel protistan lineages. These included new clades of the highest taxonomic level unrelated to any known eukaryote as well as deep branches within established protistan groups. Three novel lineages branch at the base of the eukaryotic evolutionary tree preceding, contemporary with, or immediately following the earliest eukaryotic branches. These newly discovered protists may retain traits reminiscent of an early eukaryotic ancestor(s).