Understanding trends in abundance is important to fisheries conservation, but techniques for estimating streamwide abundance of cryptic fishes with strong habitat–abundance relationships are not well established and need further development. We developed techniques for addressing this need using the Harlequin Darter Etheostoma histrio, a small, cryptic freshwater fish associated with submerged wood in streams. Our objectives were to (1) determine how Harlequin Darter abundance and the amount of submerged wood were related at sampled sites and (2) use this relationship to estimate Harlequin Darter abundance at unsampled sites and extrapolate Harlequin Darter abundance estimates and associated uncertainty streamwide. We conducted a mark–recapture study to estimate abundance of Harlequin Darters in 25‐m stream reaches at 24 sites in Big Escambia Creek (BEC) and 18 sites in Pine Barren Creek (PBC) (Escambia River tributaries in northwestern Florida). The number of wood pieces (submerged wood ≥1.5 m long and ≥0.25 m in circumference) in both creeks was counted and mapped using side‐scan sonar and a geographic information system. Harlequin Darter and wood data were used in a Bayesian multinomial mixture model to estimate site abundance of Harlequin Darters, to determine the relationship between wood and Harlequin Darter abundance, and to extrapolate Harlequin Darter abundance streamwide. We found a positive relationship between wood and Harlequin Darter abundance in both creeks, and there were more wood pieces in PBC than in BEC. Streamwide abundance of Harlequin Darters was greater in PBC than in BEC. The extrapolated streamwide abundance estimates were 9,369 Harlequin Darters (95% credible interval = 6,668–13,402) in PBC and 7,439 Harlequin Darters (95% credible interval = 4,493–11,226) in BEC. Our methods effectively estimated abundance of a small, cryptic fish that uses complex wood habitat. In addition, our findings may assist in the conservation of the Harlequin Darter.