Animals and fungi independently evolved from the protozoan phylum Choanozoa, these three groups constituting a major branch of the eukaryotic evolutionary tree known as opisthokonts. Opisthokonts and the protozoan phylum Amoebozoa (amoebae plus slime moulds) were previously argued to have evolved independently from the little-studied, largely flagellate, protozoan phylum, Sulcozoa. Sulcozoa are a likely evolutionary link between opisthokonts and the more primitive excavate flagellates that have ventral feeding grooves and the most primitive known mitochondria. To extend earlier sparse evidence for the ancestral (paraphyletic) nature of Sulcozoa, we sequenced transcriptomes from six gliding flagellates (two apusomonads; three planomonads; Mantamonas). Phylogenetic analyses of 173-192 genes and 73-122 eukaryote-wide taxa show Sulcozoa as deeply paraphyletic, confirming that opisthokonts and Amoebozoa independently evolved from sulcozoans by losing their ancestral ventral groove and dorsal pellicle: Apusozoa (apusomonads plus anaerobic breviate amoebae) are robustly sisters to opisthokonts and probably paraphyletic, breviates diverging before apusomonads; Varisulca (planomonads, Mantamonas, and non-gliding flagellate Collodictyon) are sisters to opisthokonts plus Apusozoa and Amoebozoa, and possibly holophyletic; Glissodiscea (planomonads, Mantamonas) may be holophyletic, but Mantamonas sometimes groups with Collodictyon instead. Taxon and gene sampling slightly affects tree topology; for the closest branches in Sulcozoa and opisthokonts, proportionally reducing missing data eliminates conflicts between homogeneous-model maximum-likelihood trees and evolutionarily more realistic site-heterogeneous trees. Sulcozoa, opisthokonts, and Amoebozoa constitute an often-pseudopodial 'podiate' clade, one of only three eukaryotic 'supergroups'. Our trees indicate that evolution of sulcozoan dorsal pellicle, ventral pseudopodia, and ciliary gliding (probably simultaneously) generated podiate eukaryotes from Malawimonas-like excavate flagellates.