The Clean Water Act presents a daunting task for states by requiring them to assess and restore all their waters. Traditional monitoring has led to two beliefs: (1) ad hoc sampling (i.e., non-random) is adequate if enough sites are sampled and (2) more intensive sampling (e.g., collecting more organisms) at each site is always better. We analyzed the 1,500 Maryland Biological Stream Survey (MBSS) random sites sampled in 2000-2004 to describe the variability of Index of Biotic Integrity (IBI) scores at the site, reach, and watershed scales. Average variability for fish and benthic IBI scores increased with increasing spatial scale, demonstrating that single site IBI scores are not representative at watershed scales and therefore at best 25% of a state's stream length can be representatively sampled with non-random designs. We evaluated the effects on total taxa captured and IBI precision of sampling for twice as many benthic macroinvertebrates at 73 MBSS sites with replicate samples. When sampling costs were fixed, the precision of the IBI decreased as the number of sites had to be reduced by 15%. Only 1% more taxa were found overall when the 73 sites where combined. We concluded that (1) comprehensive assessment of a state's waters should be done using probability-based sampling that allows the condition across all reaches to be inferred statistically and (2) additional site sampling effort should not be incorporated into state biomonitoring when it will reduce the number of sites sampled to the point where overall assessment precision is lower.