Spatial variation in extinction and colonization is expected to influence community composition over time. In stream fish communities, local species richness (alpha diversity) and species turnover (beta diversity) are thought to be regulated by high extinction rates in headwater streams and high colonization rates in downstream areas. We evaluated the spatiotemporal structure of fish communities in streams originally surveyed by Burton and Odum 1945 (Ecology 26: 182-194) in Virginia, USA and explored the effects of species traits on extinction and colonization dynamics. We documented dramatic changes in fish community structure at both the site and stream scales. Of the 34 fish species observed, 20 (59%) were present in both time periods, but 11 (32%) colonized the study area and three (9%) were extirpated over time. Within streams, alpha diversity increased in two of three streams but beta diversity decreased dramatically in all streams due to fish community homogenization caused by colonization of common species and extirpation of rare species. Among streams, however, fish communities differentiated over time. Regression trees indicated that reproductive life-history traits such as spawning mound construction, associations with mound-building species, and high fecundity were important predictors of species persistence or colonization. Conversely, native fishes not associated with mound-building exhibited the highest rates of extirpation from streams. Our results demonstrate that stream fish colonization and extinction dynamics exhibit hierarchical spatial structure and suggest that mound-building fishes serve as keystone species for colonization of headwater streams.