We sampled fishes and measured microhabitat in series of contiguous habitat units (riffles, runs, pools) in three Virginia streams. We used Monte Carlo simulations to construct hypothetical series of habitat units, then examined how number of species, similarity in relative abundances, and number of microhabitats accumulated with increasing number of habitat units (i.e., sampling effort). Proportions of all species and microhabitats represented were relatively low and variable at low sampling effort, but increased asymptotically and became less variable with greater sampling effort. To facilitate comparisons among streams, we fitted simulation results to negative exponential curves. The curves indicated that 90% of the species present were usually found by sampling 5 to 14 habitat units (stream length of 22–67 stream widths). Estimates of species relative abundances required less sampling effort for a given accuracy than estimates of number of species. Rates of species accumulation (with effort) varied among streams and reflected discontinuity in species distributions among habitat units. Most discontinuity seemed to be due to low population density rather than to habitat selectivity. Results from an Illinois stream corroborated our findings from Virginia, and suggested that greater sampling effort is needed to characterize fish community structure in more homogeneous stream reaches.