Permafrost thaw ponds and lakes are widespread across the northern landscape and may play a central role in global biogeochemical cycles, yet knowledge about their microbial ecology is limited. We sampled a set of thaw ponds and lakes as well as shallow rock-basin lakes that are located in distinct valleys along a north–south permafrost degradation gradient. We applied high-throughput sequencing of the 16S rRNA gene to determine co-occurrence patterns among bacterial taxa (operational taxonomic units, OTUs), and then analyzed these results relative to environmental variables to identify variables controlling bacterial community structure. Network analysis was applied to identify possible ecological linkages among the bacterial taxa and with abiotic and biotic variables. The results showed an overall high level of shared taxa among bacterial communities within each valley; however, the bacterial co-occurrence patterns were non-random, with evidence of habitat preferences. There were taxonomic differences in bacterial assemblages among the different valleys that were statistically related to dissolved organic carbon concentration, conductivity and phytoplankton biomass. Co-occurrence networks revealed complex interdependencies within the bacterioplankton communities and showed contrasting linkages to environmental conditions among the main bacterial phyla. The thaw pond networks were composed of a limited number of highly connected taxa. This “small world network” property would render the communities more robust to environmental change but vulnerable to the loss of microbial “keystone species”. These highly connected nodes (OTUs) in the network were not merely the numerically dominant taxa, and their loss would alter the organization of microbial consortia and ultimately the food web structure and functioning of these aquatic ecosystems.