Most assessments of the effectiveness of river restoration are done at small spatial scales (<10 km) over short time frames (less than three years), potentially failing to capture large-scale mechanisms such as completion of life-history processes, changes to system productivity, or time lags of ecosystem responses. To test the hypothesis that populations of two species of large-bodied, piscivorous, native fishes would increase in response to large-scale structural habitat restoration (reintroduction of 4,450 pieces of coarse woody habitat into a 110-km reach of the Murray River, southeastern Australia), we collected annual catch, effort, length, and tagging data over seven years for Murray cod (Maccullochella peelii) and golden perch (Macquaria ambigua) in a restored “intervention” reach and three neighboring “control” reaches. We supplemented mark–recapture data with telemetry and angler phone-in data to assess the potentially confounding influences of movement among sampled populations, heterogeneous detection rates, and population vital rates. We applied a Bayesian hierarchical model to estimate changes in population parameters including immigration, emigration, and mortality rates. For Murray cod, we observed a threefold increase in abundance in the population within the intervention reach, while populations declined or fluctuated within the control reaches. Golden perch densities also increased twofold in the intervention reach. Our results indicate that restoring habitat heterogeneity by adding coarse woody habitats can increase the abundance of fish at a population scale in a large, lowland river. Successful restoration of poor-quality “sink” habitats for target species relies on connectivity with high-quality “source” habitats. We recommend that the analysis of restoration success across appropriately large spatial and temporal scales can help identify mechanisms and success rates of other restoration strategies such as restoring fish passage or delivering water for environmental outcomes.