Abstract Systematic methods for prioritizing the repair and removal of fish passage barriers, while growing of late, have hitherto focused almost exclusively on meeting the needs of migratory fish species (e.g., anadromous salmonids). An important but as of yet unaddressed issue is the development of new modeling approaches which are applicable to resident fish species habitat restoration programs. In this paper, we develop a budget constrained optimization model for deciding which barriers to repair or remove in order to maximize habitat availability for stream resident fish. Habitat availability at the local stream reach is determined based on the recently proposed C metric, which accounts for the amount, quality, distance and level of connectivity to different stream habitat types. We assess the computational performance of our model using geospatial barrier and stream data collected from the Pine-Popple Watershed, located in northeast Wisconsin (USA). The optimization model is found to be an efficient and practical decision support tool. Optimal solutions, which are useful in informing basin-wide restoration planning efforts, can be generated on average in only a few minutes.