The taxonomic composition of egg-associated microbial communities can play a crucial role in the development of fish embryos. In response, hosts increasingly influence the composition of their associated microbial communities during embryogenesis, as concluded from recent field studies and laboratory experiments. However, little is known about the taxonomic composition and the diversity of egg-associated microbial communities within ecosystems; e.g., river networks. We sampled late embryonic stages of naturally spawned brown trout at nine locations within two different river networks and applied 16S rRNA pyrosequencing to describe their bacterial communities. We found no evidence for a significant isolation-by-distance effect on the composition of bacterial communities, and no association between neutral genetic divergence of fish host (based on 11 microsatellites) and phylogenetic distances of the composition of their associated bacterial communities. We characterized core bacterial communities on brown trout eggs and compared them to corresponding water samples with regard to bacterial composition and its presumptive function. Bacterial diversity was positively correlated with water temperature at the spawning locations. We discuss this finding in the context of the increased water temperatures that have been recorded during the last 25 years in the study area.