The network architecture of streams and rivers constrains evolutionary, demographic and ecological processes of freshwater organisms. This consistent architecture also makes stream networks useful for testing general models of population genetic structure and the scaling of gene flow. We examined genetic structure and gene flow in the facultatively paedomorphic Idaho giant salamander, Dicamptodon aterrimus, in stream networks of Idaho and Montana, USA. We used microsatellite data to test population structure models by (i) examining hierarchical partitioning of genetic variation in stream networks; and (ii) testing for genetic isolation by distance along stream corridors vs. overland pathways. Replicated sampling of streams within catchments within three river basins revealed that hierarchical scale had strong effects on genetic structure and gene flow. amova identified significant structure at all hierarchical scales (among streams, among catchments, among basins), but divergence among catchments had the greatest structural influence. Isolation by distance was detected within catchments, and in-stream distance was a strong predictor of genetic divergence. Patterns of genetic divergence suggest that differentiation among streams within catchments was driven by limited migration, consistent with a stream hierarchy model of population structure. However, there was no evidence of migration among catchments within basins, or among basins, indicating that gene flow only counters the effects of genetic drift at smaller scales (within rather than among catchments). These results show the strong influence of stream networks on population structure and genetic divergence of a salamander, with contrasting effects at different hierarchical scales.