Cercomonads (=Cercomonadida) are biflagellate gliding bacterivorous protozoa, abundant and diverse in soil and freshwater. We establish 56 new species based on 165 cultures, differential interference contrast microscopy, and 18S and ITS2 rDNA sequencing, and a new genus Cavernomonas studied by scanning electron microscopy. We fundamentally revise the phylogeny and classification of cercomonad Cercozoa. We describe 40 Cercomonas species (35 novel), six Eocercomonas (five novel), two Cavernomonas, and 18 Paracercomonas species (14 novel). We obtained additional cercomonad clade A (Cercomonas, Eocercomonas, Cavernomonas) sequences from multiple environmental DNA libraries. The most commonly cultivated genotypes are not the commonest in environmental DNA, suggesting that cercomonad ecology is far more complex than implied by laboratory cultures. Cercomonads have never been isolated from saline environments, although some species can grow in semi-saline media in the laboratory, and environmental DNA libraries regularly detect them in coastal marine sediments. The first ultrastructural study of an anaerobic cercozoan, Paracercomonas anaerobica sp. nov., a highly divergent cercomonad, shows much simpler ciliary roots than in clade A cercomonads, a ciliary hub-lattice and axosome, and mitochondria with tubular cristae, consistent with it being only facultatively anaerobic. We also describe Agitata tremulans gen. et sp. nov., previously misidentified as Cercobodo (=Dimastigamoeba) agilis Moroff.