Surface water (SW) is a critical resource in semi-arid areas. The Murray-Darling Basin (MDB) of Australia, one of the largest semi-arid basins in the world has suffered significant water shrinkages during the Millennium Drought (1999-2009), followed by extensive flooding. To synoptically quantify changes in SW extent and flooding dynamics over MDB, we used seasonally continuous Landsat TM and ETM+ data (1986 – 2011) and generic machine learning algorithms. We further mapped flooded forest at a riparian forest site that experienced severe tree dieback due to changes in flooding regime. We used a stratified sampling design to assess the accuracy of the SW product across time. Accuracy assessment yielded an overall classification accuracy of 99.94%, with producer’s and user’s accuracy of SW of 85.4% and 97.3%, respectively. Overall accuracy was the same for Landsat 5 and 7 data but user’s and producer’s accuracy of water were higher for Landsat 7 than 5 data and stable over time. Our validated results document a rapid loss in SW. The number, size, and total area of SW showed high seasonal variability with highest numbers in winter and lowest numbers in summer. SW extent per season per year showed high interannual and seasonal variability, with low seasonal variability during the Millennium Drought. The approach developed here is globally applicable, relevant to areas with competing water demands (e.g. Okavango River delta, Mekong River Basin).