Planctomycetes, a unique group of widespread and understudied bacteria, are known to be associated with macroalgae. The temporal dynamics and the host-specific association of planctomycetal communities on Fucus spiralis, Ulva sp. and Chondrus crispus from two locations in the North Coast of Portugal were assessed both by denaturing gradient gel electrophoresis with group-specific primers and 16S rDNA amplicon libraries. The epiphytic planctomycetal communities showed a significant association with the host macroalgal species independently of the geographical location and the season. This pattern was confirmed by clone libraries of winter and summer samples: we obtained 720 16S rRNA gene sequences that represented 44 operational taxonomic units (OTUs) within the phylum Planctomycetes. Most of the OTUs belonged to Blastopirellula, followed by Rhodopirellula, Planctomyces, the Pir4 lineage and the uncultured class OM190 (this last one nearly 30% of the OTUs). Ulva sp. and C. crispus had more diverse planctomycetal communities than F. spiralis. Analysis of beta diversity showed that the planctomycetal microbiome was host specific. We hypothesize that the specific association of Planctomycetes and their macroalgal hosts is likely determined by nutritional molecules provided by the algae and the set of sulfatases inherent to each Planctomycetes species.