Pacific Ocean sea surface temperatures (SST) influence rainfall variability on multidecadal and interdecadal timescales in concert with the Pacific Decadal Oscillation (PDO) and Interdecadal Pacific Oscillation (IPO). Rainfall variations in locations such as Australia and North America are therefore linked to phase changes in the PDO. Furthermore, studies have suggested teleconnections exist between the western Indian Ocean and Pacific Decadal Variability (PDV), similar to those observed on interannual timescales related to the El Ni o Southern Oscillation (ENSO). However, as instrumental records of rainfall are too short and sparse to confidently assess multidecadal climatic teleconnections, here we present four coral climate archives from Madagascar spanning up to the past 300 yr (1708–2008) to assess such decadal variability. Using spectral luminescence scanning to reconstruct past changes in river runoff, we identify significant multidecadal and interdecadal frequencies in the coral records, which before 1900 are coherent with Asian-based PDO reconstructions. This multidecadal relationship with the Asian-based PDO reconstructions points to an unidentified teleconnection mechanism that affects Madagascar rainfall/runoff, most likely triggered by multidecadal changes in North Pacific SST, influencing the Asian Monsoon circulation. In the 20th century we decouple human deforestation effects from rainfall-induced soil erosion by pairing luminescence with coral geochemistry. Positive PDO phases are associated with increased Indian Ocean temperatures and runoff/rainfall in eastern Madagascar, while precipitation in southern Africa and eastern Australia declines. Consequently, the negative PDO phase that started in 1998 may contribute to reduced rainfall over eastern Madagascar and increased precipitation in southern Africa and eastern Australia. We conclude that multidecadal rainfall variability in Madagascar and the western Indian Ocean needs to be taken into account when considering water resource management under a future warming climate.