Animals and microorganisms often establish close ecological relationships. However, much of our knowledge on animal microbiomes comes from two deeply studied groups: vertebrates and arthropods. To understand interactions on a broader scale of diversity, we characterized the bacterial microbiomes of close to 1,000 microscopic marine invertebrates from 21 phyla, covering most of the remaining tree of metazoans. Samples were collected from five temperate and tropical locations covering three marine habitats (sediment, water column and intertidal macroalgae) and bacterial microbiomes were characterized using 16S rRNA gene sequencing. Our data show that, despite their size, these animals harbour bacterial communities that differ from those in the surrounding environment. Distantly related but coexisting invertebrates tend to share many of the same bacteria, suggesting that guilds of microorganisms preferentially associated with animals, but not tied to any specific host lineage, are the main drivers of the ecological relationship. Host identity is a minor factor shaping these microbiomes, which do not show the kind of correlation with host phylogeny, or “phylosymbiosis”, observed in many large animals. Hence, the current debate on the varying strength of phylosymbiosis within selected lineages should be reframed to account for the possibility that such a pattern might be the exception rather than the rule.