Nephridial (excretory organ) symbionts are widespread in lumbricid earthworms and the complexity of the nephridial symbiont communities varies greatly between earthworm species. The two most common symbionts are the well-described Verminephrobacter and less well-known Flexibacter-like bacteria. Verminephrobacter are present in almost all lumbricid earthworms, they are species-specific, vertically transmitted, and have presumably been associated with their hosts since the origin of lumbricids. Flexibacter-like symbionts have been reported from about half the investigated earthworms; they are also vertically transmitted. To investigate the evolution of this tri-partite symbiosis, phylogenies for 18 lumbricid earthworm species were constructed based on two mitochondrial genes, NADH dehydrogenase subunit 2 (ND2) and cytochrome c oxidase subunit I (COI), and compared to their symbiont phylogenies based on RNA polymerase subunit B (rpoB) and 16S rRNA genes.The two nephridial symbionts showed markedly different evolutionary histories with their hosts. For Verminephrobacter, clear signs of long-term host-symbiont co-evolution with rare host switching events confirmed its ancient association with lumbricid earthworms, likely dating back to their last common ancestor about 100 million years (MY) ago. In contrast, phylogenies for the Flexibacter-like symbionts suggested an ability to switch to new hosts, to which they adapted and subsequently became species-specific. Putative co-speciation events were only observed with closely related host species; on that basis, this secondary symbiosis was estimated to be minimum 45 MY old. Based on the monophyletic clustering of the Flexibacter-like symbionts, the low 16S rRNA gene sequence similarity to the nearest described species (<92%) and environmental sequences (<94.2 %), and the specific habitat in the earthworm nephridia, we propose a new candidate genus for this group, Candidatus Nephrothrix.