River biofilms dominated by Phormidium (cyanobacteria) are receiving increased attention worldwide because of a recent expansion in their distribution and their ability to produce neurotoxins leading to animal mortalities. Limited data are available on the composition and structure of bacterial communities (BCs) associated with Phormidium biofilms despite the important role they potentially play in biofilm functioning. By using a high-throughput sequencing approach, we compared the BCs associated with Phormidium biofilms in several sampling sites of the Tarn River (France) and in eight New Zealand rivers. The structure of the BCs from both countries displayed spatial and temporal variations but were well conserved at the order level and 28% of the OTUs containing 90% of the reads were shared by these BCs. This suggests that micro-environmental conditions occurring within thick Phormidium biofilms strongly shape the associated BCs. A strong and significant distance-decay relationship (rp = 0.7; P = 0.001) was found in BCs from New Zealand rivers but the Bray-Curtis dissimilarities between French and New Zealand BCs are in the same order of magnitude of those found between New Zealand BCs. All these findings suggest that local environmental conditions seem to have more impact on BCs than dispersal capacities of bacteria.