Rab GTPases serve as major control elements in the coordination and definition of specific trafficking steps and intracellular compartments. Rab activity is modulated in part by GTPase-activating proteins (GAPs), and many RabGAPs share a Tre-2/Bub2/Cdc16 (TBC)–domain architecture, although the majority of TBC proteins are poorly characterized. We reconstruct the evolutionary history of the TBC family using ScrollSaw, a method for the phylogenetic analysis of pan-eukaryotic data sets, and find a sophisticated, ancient TBC complement of at least 10 members. Significantly, the TBC complement is nearly always smaller than the Rab cohort in any individual genome but also suggests Rab/TBC coevolution. Further, TBC-domain architecture has been well conserved in modern eukaryotes. The reconstruction also shows conservation of ancestral TBC subfamilies, continuing evolution of new TBCs, and frequent secondary losses. These patterns give additional insights into the sculpting of the endomembrane system.