Abstract Habitat availability is often regarded as the primary factor that limits population and community recovery in degraded ecosystems, and physical habitat is thus often targeted in restoration. The identification of which habitat(s) to attempt to restore is a critical step in the restoration process, but one for which there is often a paucity of useful information. Here we examine the distribution of fish in three lowland streams in Victoria, Australia, that have been degraded by severe sedimentation. We aim to identify habitats that are associated with high abundances of native fish, and that thus might be appropriate to target in habitat restoration. Associations between native fish abundances and physical habitat characteristics were examined at three spatial scales (among streams, among sites and within sites) to determine the types of habitat to which fish respond, and the scales over which these responses occur. Of the four species of native fish found in the streams, three (Galaxias olidus Günther, Gadopsis marmoratus (Richardson) and Nanoperca australis Günther) showed significant habitat associations at small spatial scales (i.e. within sites). In particular, these species were generally found in deeper water, and in close proximity to cover (typically either coarse or fine woody debris or vegetation). Differences in habitat availability among sites and streams were less influential, except in the case of G. marmoratus, which was completely absent from both the ephemeral streams. Although our results suggest that these species collectively respond to habitat at several spatial scales, fish distributions were allied to the presence of habitat structure at the scale of metres, the smallest spatial scale examined. We hypothesize that fish abundances are currently limited by the low availability of habitat at these small spatial scales. It may therefore be possible to increase fish abundances in these creeks by augmenting the amount of available habitat via stream restoration.