The 1997–2009 Millennium drought changed the rainfall-runoff response across large parts of Victoria in south-eastern Australia. This study investigates the hydrological non-stationarity in Victoria, using water balance analysis and a modelling experiment with observed hydroclimate and remotely sensed data over 1982–2020 from 120 catchments. Most catchments in Victoria exhibit hydrological non-stationarity, where there is less streamflow generated during, and for many catchments even after, the drought from the same amount of annual rainfall. This can be partly explained by the low percentage reduction in actual evapotranspiration (AET) during the drought compared to the percentage reduction in rainfall, causing the large reduction in streamflow which is a small difference between rainfall minus AET. There is also an underlying greening trend that has been only partly stalled during the Millennium drought. The AET is higher in the post-drought period compared to the pre-drought period, suggesting that the proportion of rainfall that becomes streamflow may continue to decline if the greening trend continues. The observed hydrological non-stationarity is much more significant in North-West Victoria, where the 15% lower mean annual rainfall over the Millennium drought translated to 80% reduction in mean annual streamflow. This can be partly explained by the lower rainfall and low runoff coefficient in the region. The catchments in North-West Victoria have not fully recovered from the Millennium drought. Rainfall-runoff models that consider multi-year lags in the rainfall, as well as improvements in the AET conceptualisation and baseflow generation only above a subsurface store threshold, also simulates runoff much more robustly in North-West Victoria, compared to elsewhere in Victoria. The water balance analysis and modelling exploration suggest that the hydrological regime in North-West Victoria may have shifted, and it may be more prudent to use the post-1997 hydrological baseline for modelling and water resources planning for the region.