We investigated changes in sediment bacterial community structure across a spatial organic enrichment gradient associated with fish farms in two different sites in the Eastern Mediterranean (Greece). The observed trend was similar at both fish farms even though they are far from each other. The mean number of the most abundant operational taxonomic units (OTUs) was not significantly different, either among samples across the organic enrichment gradient or between impacted and control samples at both fish farms. Nevertheless, community structure differed both within each site (impacted vs. control samples) and between the two sites. We found that most of between-site differences in community structure could be attributed to differences in grain size, redox potential of the sediment, and, to a lesser extent, chlorophyll α, while within-site differences were attributed to the distance from the cage and the median grain size. Sequenced DGGE bands that were present only at samples directly beneath the cages, affiliated with different phylogenetic groups at each site. These results indicate that aquaculture effluents affect the structure of sediment bacterial communities, but without any apparent impact on the number of the most abundant OTUs.