Assessing the passage of aquatic organisms through culvert road crossings has become increasingly common in efforts to restore stream habitat. Several federal and state agencies and local stakeholders have adopted assessment approaches based on literature-derived criteria for culvert impassability. However, criteria differ and are typically specific to larger-bodied fishes. In an analysis to prioritize culverts for remediation to benefit imperiled, small-bodied fishes in the Upper Coosa River system in the southeastern United States, we assessed the sensitivity of prioritization to the use of differing but plausible criteria for culvert impassability. Using measurements at 256 road crossings, we assessed culvert impassability using four alternative criteria sets represented in Bayesian belief networks. Two criteria sets scored culverts as either passable or impassable based on alternative thresholds of culvert characteristics (outlet elevation, baseflow water velocity). Two additional criteria sets incorporated uncertainty concerning ability of small-bodied fishes to pass through culverts and estimated a probability of culvert impassability. To prioritize culverts for remediation, we combined estimated culvert impassability with culvert position in the stream network relative to other barriers to compute prospective gain in connected stream habitat for the target fish species. Although four culverts ranked highly for remediation regardless of which criteria were used to assess impassability, other culverts differed widely in priority depending on criteria. Our results emphasize the value of explicitly incorporating uncertainty into criteria underlying remediation decisions. Comparing outcomes among alternative, plausible criteria may also help to identify research most needed to narrow management uncertainty.