Deciphering the colonization processes by which introduced pests invade new areas is essential to limit the risk of further expansion and/or multiple introductions. We here studied the invasion history of the maritime pine bast scale Matsucoccus feytaudi. This host-specific insect does not cause any damage in its native area, but it devastated maritime pine forests of South-Eastern France where it was detected in the 1960s, and since then reached Italy and Corsica. We used population genetic approaches to infer the populations’ recent evolutionary history from microsatellite markers and Approximate Bayesian Computation. Consistent with previous mitochondrial data, we showed that the native range is geographically strongly structured, which is probably due to the patchy distribution of the obligate host and the limited dispersal capacity of the scale. Our results show that the invasion history can be described in three successive steps involving different colonization and dispersal processes. During the mid-XXth century, massive introductions occurred from the Landes planted forest to South-Eastern France, probably due to transportation of infested wood material after World War II. Stepping-stone expansion, consistent with natural dispersal, then allowed M. feytaudi to reach the maritime pine forests of Liguria and Tuscany in Italy. The island of Corsica was accidentally colonized in the 1990s, and the most plausible scenario involves the introduction of a limited number of migrants from the forests of South-Eastern France and Liguria, which is consistent with an aerial dispersal due to the dominant winds that blow in spring in this region.