We investigated stream fish assemblages in Nebraska and Kansas to determine the effects of habitat and sampling methodologies on the community structure and abundance of prairie stream fishes of the Great Plains. We intensively sampled four mid-sized (9.9 m to 28.9 m wide), wadable streams to determine the sampling effort needed to assess the status and trends of fish communities. The number of reaches (<1 km) required to estimate segment (20-30 km) species richness decreased with increased reach length (10, 20, 40, or 60 mean stream width [MSW]) whereas total sampling effort decreased with more and shorter reaches. Only after all 10 reaches was total species richness obtained with 40 to 60 MSW. The number of reaches needed to detect 50% changes in fish relative abundance at 0.8 statistical power was 99 (range 7-630) and decreased with increased reach length. A greater number of reaches was needed to detect 90% of species richness and 25% changes in relative abundance when community similarity and habitat heterogeneity was lower. Our results suggest homogenous stream segments require more reaches to characterize fish community structure and monitor trends in fish abundance and a greater number of shorter reaches may be better than fewer longer (e.g. 40 or larger MSW) reaches. Effects of local environmental influences on the structure of fish assemblages were evaluated from 159 sites in two regions of the Great Plains with limited anthropogenic disturbance. These least disturbed regions offered an opportunity to evaluate the structure and natural variation of streams and fish assemblages within the Great Plains. We used canonical correspondence analyses to determine the influence of environmental conditions on species abundances, species occurrences, and assemblage characteristics. Analysis of regions separately indicated that similar environmental factors structured streams and fish assemblages, despite differences in environmental conditions and species composition between regions. Variance in fish abundance and assemblage characteristic data from both regions was best explained by metrics of stream size and habitat features linked with stream size (width, depth, conductivity, instream cover). Our results provide a framework and reference for least disturbed conditions and assemblage structure in North American prairie streams.