Global environmental change has implications for the spatial and temporal distribution of water resources, but quantifying its effects remains a challenge. The impact of vegetation responses to increasing atmospheric CO2 concentrations on the hydrologic cycle is particularly poorly constrained. Here we combine remotely sensed normalized difference vegetation index (NDVI) data and long-term water-balance evapotranspiration (ET) measurements from 190 unimpaired river basins across Australia during 1982-2010 to show that the precipitation threshold for water limitation of vegetation cover has significantly declined during the past three decades, whereas sub-humid and semi-arid basins are not only greening but also consuming more water, leading to significant (24-28%) reductions in streamflow. In contrast, wet and arid basins show nonsignificant changes in NDVI and reductions in ET. These observations are consistent with expected effects of elevated CO2 on vegetation. They suggest that projected future decreases in precipitation are likely to be compounded by increased vegetation water use, further reducing streamflow in water-stressed regions.