The phytoplankton species Gymnodinium catenatum is responsible for major worldwide losses in aquaculture due to shellfish toxicity. On the West coast of the Iberian Peninsula, toxic blooms have been reported since the mid-1970s. While the recent geographical spread of this species into Australasia has been attributed to human-mediated introduction, its origin in the Northeast Atlantic is still under debate. Gymnodinium catenatum forms a highly resistant resting stage (cyst) that can be preserved in coastal sediments, building-up an historical record of the species. Similar cyst types (termed microreticulate) are produced by other non-toxic Gymnodinium species that often co-occur with G. catenatum. We analysed the cyst record of microreticulate species in dated sediment cores from the West Iberian shelf covering the past ca. 150 years. Three distinct morphotypes were identified on the basis of cyst diameter and paracingulum reticulation. These were attributed to G. catenatum (35.6–53.3 μm), G. nolleri (23.1–36.4 μm), and G. microreticulatum (20.5–34.3 μm). Our results indicate that G. catenatum is new to the NE Atlantic, where it appeared by 1,889 ± 10, expanding northwards along the West Iberian coast. The earliest record is from the southernmost sample, while in the central Portuguese shelf the species appears in sediments dated to 1,933 ± 3, and in the North, off Oporto, in 1,951 ± 4. On the basis of the cyst record and toxic bloom reports, we reconstruct the invasive pathway of G. catenatum in the NE Atlantic. Although human-mediated introduction cannot be discarded, the available evidence points towards natural range expansion, possibly from NW Africa.