The siphonous green seaweed Bryopsis harbors complex intracellular bacterial communities. Previous studies demonstrated that certain species form close, obligate associations with Flavobacteriaceae. A predominant imprint of host evolutionary history on the presence of these bacteria suggests a highly specialized association. In this study we elaborate on previous results by expanding the taxon sampling and testing for host-symbiont coevolution Therefore, we optimized a PCR protocol to directly and specifically amplify Flavobacteriaceae endosymbiont 16S rRNA gene sequences, which allowed us to screen a large number of algal samples without the need for cultivation or surface sterilization. We analyzed 146 Bryopsis samples, and 92 additional samples belonging to the Bryopsidales and other orders within the class Ulvophyceae. Results indicate that the Flavobacteriaceae endosymbionts are restricted to Bryopsis, and only occur within specific, warm-temperate and tropical clades of the genus. Statistical analyses (AMOVA) demonstrate a significant non-random host-symbiont association. Comparison of bacterial 16S rRNA and Bryopsis rbcL phylogenies, however, reveal complex host-symbiont evolutionary associations, whereby closely related hosts predominantly harbor genetically similar endosymbionts. Bacterial genotypes are rarely confined to a single Bryopsis species and most Bryopsis species harbored several Flavobacteriaceae, obscuring a clear pattern of coevolution.