The symbiosis between bacteria and sponges has arguably the longest evolutionary history for any extant metazoan lineage, yet little is known about bacterial evolution or adaptation in this process. An example of often dominant and widespread bacterial symbionts of sponges is a clade of uncultured and uncharacterised Proteobacteria. Here we set out to characterise this group using metagenomics, in-depth phylogenetic analyses, metatranscriptomics, and fluorescence in situ hybridisation microscopy. We obtained five metagenome-assembled-genomes (MAGs) from different sponge species that, together with a previously published MAG (AqS2), comprise two families within a new gammaproteobacterial order that we named UTethybacterales. Members of this order share a heterotrophic lifestyle but vary in their predicted ability to use various carbon, nitrogen and sulfur sources, including taurine, spermidine and dimethylsulfoniopropionate. The deep branching of the UTethybacterales within the Gammaproteobacteria and their almost exclusive presence in sponges suggests they have entered a symbiosis with their host relatively early in evolutionary time and have subsequently functionally radiated. This is reflected in quite distinct lifestyles of various species of UTethybacterales, most notably their diverse morphologies, predicted substrate preferences, and localisation within the sponge tissue. This study provides new insight into the evolution of metazoan–bacteria symbiosis.