Some microplanktonic species, mostly dinoflagellates, causing Harmful Algal Blooms (HABs), produce toxins which may affect the environment and human health, thus causing important economic losses. The dinoflagellate Pyrodinium bahamense var. compressum is one of the main species causing harmful algal blooms along the tropical Pacific. Although it was first reported along the Mexican coast in the 1970s, here we report that a sedimentary record of Pyrodinium cysts from the Gulf of Tehuantepec in the tropical East Pacific (Mexico), which spans from the 1860s, showed the continuous occurrence of Pyrodinium cysts and that their presence has been declining in the last few decades. Although Pyrodinium HABs have been attributed to El Niño events in the tropical Indo-West Pacific, the record shows that most blooms in the tropical East Pacific appear in periods of low sea surface temperature and higher rainfall, as can be observed during rapid shifts from cold (La Niña) to warm (El Niño) conditions in that region. This mechanism offers new ways to better predict and facilitate early detection of Pyrodinium HABs worldwide.