Historically known as the yellow fever mosquito, Aedes aegypti invaded Madeira Island in 2005 and was the vector of the island's first dengue outbreak in 2012. We have studied genetic variation at 16 microsatellites and two mitochondrial DNA genes in temporal samples of Madeira Island, in order to assess the origin of the invasion and the population structure of this mosquito vector. Our results indicated at least two independent colonization events occurred on the island, both having a South American source population. In both scenarios, Venezuela was the most probable origin of these introductions, a result that is in accordance with the socioeconomic relations between this country and Madeira Island. Once introduced, Ae. aegypti has rapidly expanded along the southern coast of the island and reached a maximum effective population size (Ne) in 2012, coincident with the dengue epidemic. After the outbreak, there was a 10-fold reduction in Ne estimates, possibly reflecting the impact of community-based vector control measures implemented during the outbreak. These findings have implications for mosquito surveillance not only for Madeira Island, but also for other European regions where Aedes mosquitoes are expanding.