In-stream barriers, such as dams, culverts and diversions alter hydrologic processes and aquatic habitat. Removing uneconomical and aging in-stream barriers to improve stream habitat is increasingly used in river restoration. Previous barrier removal projects focused on score-and-rank techniques, ignoring cumulative change and spatial structure of barrier networks. Likewise, most water supply models prioritize either human water uses or aquatic habitat, failing to incorporate both human and environmental water use benefits. In this study, a dual objective optimization model prioritized removing in-stream barriers to maximize aquatic habitat connectivity for trout, using streamflow, temperature, channel gradient, and geomorphic condition as indicators of aquatic habitat suitability. Water scarcity costs are minimized using agricultural and urban economic penalty functions, and a budget constraint monetizes costs of removing small barriers like culverts and diversions. The optimization model is applied to a case study in Utah’s Weber River Basin to prioritize removing barriers most beneficial to aquatic habitat connectivity for Bonneville cutthroat trout, while maintaining human water uses. Solutions to the dual objective problem quantify and graphically show tradeoffs between connected quality-weighted habitat for Bonneville cutthroat trout and economic water uses. Removing 54 in-stream barriers reconnects about 160 km of quality-weighted habitat and costs approximately $10 M, after which point the cost effectiveness of removing barriers to connect river habitat decreases. The set of barriers prioritized for removal varied monthly depending on limiting habitat conditions for Bonneville cutthroat trout. This research helps prioritize barrier removals and future restoration project decisions within the Weber Basin. The modeling approach expands current barrier removal optimization methods by explicitly including both economic and environmental water uses and is generalizable to other basins.