β-diversity is often measured over both spatial and temporal gradients of elevation, latitude, and environmental conditions. It is of particular interest to ecologists, as it provides opportunities to test and infer potential causal mechanisms determining local species assemblages. However, studies of invertebrate β-diversity, especially aquatic insects, have lagged far behind other biota. Using partial Mantel tests, we explored the associations between β-diversity of insects found in the coastal streams of Alabama, USA, and stream conditions and distances among sites. β-diversity was expressed using the Sørensen index, βSor, stream conditions were expressed as principal components (PCs), and distances as Euclidean distances (km) among sites. We also investigated the impact of seasonality (fall, summer) and taxonomic resolution (genus, species) on βSor. Regardless of season, βSor was significantly correlated (p < 0.01; r > 0.44) with stream conditions (stream size and water chemistry), while taxonomic resolution had minimal effect on associations between βSor and stream conditions. Distance was never correlated with changes in βSor (p > 0.05). We extended the use of the Sørensen pair-wise index to a multiple-site dissimilarity, βMult, which was partitioned into patterns of spatial turnover (βTurn) and nestedness (βNest). Changes in βMult were driven mostly by turnover rather than nestedness.