The tripartite ATP-independent periplasmic (TRAP) transporters are an unusual type of secondary transport system that relies on a substrate-binding protein (SBP) to achieve higher solute affinity. TRAP transporters consist of two transmembrane Q and M proteins as well as one SBP of either the DctP or the TAXI families, and are present across most major clades of Archaea and Bacteria but absent in Eukaryotes. Recent work in characterising TRAP systems has mostly focused on functional and structural aspects, whereas knowledge of their evolution and extant diversity across prokaryotes remains limited.  We conducted a genomic census of TRAP transporters across over 6,000 complete reference genomes of Archaea and Bacteria, providing a comprehensive view of the distribution and diversity of the TRAP family throughout the prokaryotic world. Our survey reveals the presence of DctP-TRAP transporters in numerous archaeal genomes, challenging the traditional view that only TAXI-TRAP exist in these lineages with a new paradigm that both SBPs are encountered across Domains. We highlight a deep sequence divergence in transmembrane components and a strong signal of their co-evolution with SBPs, showing that DctP-type and TAXI-type systems had likely already diverged by the time of LUCA. We then characterise the different sub-lineages of TRAP transporters that underpin the highly variable number of TRAP operons encoded across genomes, including between closely related species, and relate these sub-lineages to phenotypic and ecological factors. These results provide clearer insights into the diversity of TRAP transporters, informing the ongoing research on these systems as potential antimicrobial drug targets.