The Southeast Indian Ocean is a global hotspot for marine heatwaves. In that region, marine heatwaves/cold-spells are known as Ningaloo Niño/Niña events, and have substantial impacts on regional climate anomalies and unique marine ecosystems. However, the strength of Ningaloo Niño/Niña events is nonstationary and varies considerably at multidecadal timescales. Here we find that the interdecadal fluctuations in Ningaloo Niño/Niña strength are modulated by the Atlantic Multidecadal Oscillation (AMO), with strengthened (weakened) Ningaloo Niño/Niña corresponding to a positive (negative) AMO phase. During the positive AMO phase, the Atlantic warm sea surface temperature (SST) anomalies drive a series of climate mean-state changes in the Indo-Pacific region through tropics-wide teleconnections, including SST cooling over the central Pacific and SST warming in the tropical eastern Indian Ocean. Those mean-state changes tend to enhance El Niño-Southern Oscillation (ENSO)-related atmospheric and oceanic teleconnections to the Southeast Indian Ocean, and increase local Indian Ocean ocean–atmosphere coupling, promoting the Ningaloo Niño/Niña growth. Our findings highlight the critical role of the remote influence of AMO in understanding the Southeast Indian Ocean marine heatwaves/cold-spells and associated climatic and socioeconomic impacts.