Nestedness of faunal assemblages is a multi-scale phenomenon, potentially influenced by a variety of factors. Prior small-scale studies have found freshwater fish species assemblages to be nested along stream courses as a result of either selective colonization or extinction. However, within-stream gradients in temperature and other factors are correlated with the distributions of many fish species and may also contribute to nestedness. At a regional level, strongly nested patterns would require a consistent set of structuring mechanisms across streams, and correlation among species’ tolerances of the environmental factors that influence distribution. Thus, nestedness should be negatively associated with the spatial extent of the region analyzed and positively associated with elevational gradients (a correlate of temperature and other environmental factors). We examined these relationships for the freshwater fishes of Virginia. Regions were defined within a spatial hierarchy and included whole river drainages, portions of drainages within physiographic provinces, and smaller subdrainages. In most cases, nestedness was significantly stronger in regions of smaller spatial extent and in regions characterized by greater topographic relief. Analysis of hydrologic variability and patterns of faunal turnover provided no evidence that inter-annual colonization/extinction dynamics contributed to elevational differences in nestedness. These results suggest that, at regional scales, nestedness is influenced by interactions between biotic and abiotic factors, and that the strongest nestedness is likely to occur where a small number of organizational processes predominate, i.e., over small spatial extents and regions exhibiting strong environmental gradients.