During 1950–2006, austral autumn rainfall over the south-eastern Australian state of Victoria decreased by about 40% from its long-term seasonal average. The dynamics of this decline are not understood. We show that the reduction predominantly occurs in May, with variations of rainfall linked to two sources of sea surface temperature (SST) variability. A higher SST in the Indonesian Throughflow region, which occurs as the Indo-Pacific system enters into La Niña-like conditions, is associated with a rainfall increase over northern Victoria. An SST variability pattern with a positive anomaly in the central southern Indian Ocean (IO) and a negative anomaly in the subtropical IO are linked to atmospheric wave-trains, with a low pressure center over Victoria, is conducive to a rainfall increase. The weakening of the wave-trains since 1950, and an increase (reduction) in El Niño (La Niña) events, contribute to the rainfall decline. Possible influences from climate change forcing are discussed.