Background: Aedes aegypti is the most important vector of dengue fever in Brazil, where severe epidemics have recently taken place. Ae. aegypti in Brazil was the subject of an intense eradication program in the 1940s and 50s to control yellow fever. Brazil was the largest country declared free of this mosquito by the Pan-American Health Organization in 1958. Soon after relaxation of this program, Ae. aegypti reappeared in this country, and by the early 1980s dengue fever had been reported. The aim of this study is to analyze the present-day genetic patterns of Ae. aegypti populations in Brazil. Methodology/Principal Findings: We studied the genetic variation in samples of 11 widely spread populations of Ae. aegypti in Brazil based on 12 well-established microsatellite loci. Our principal finding is that present-day Brazilian Ae. aegypti populations form two distinct groups, one in the northwest and one in the southeast of the country. These two groups have genetic affinities to northern South American countries and the Caribbean, respectively. This is consistent with what has been reported for other genetic markers such as mitochondrial DNA and allele frequencies at the insecticide resistance gene, kdr. Conclusions/Significance: We conclude that the genetic patterns in present day populations of Ae. aegypti in Brazil are more consistent with a complete eradication of the species in the recent past followed by re-colonization, rather than the alternative possibility of expansion from residual pockets of refugia. At least two colonizations are likely to have taken place, one from northern South American countries (e.g., Venezuela) that founded the northwestern group, and one from the Caribbean that founded the southeastern group. The proposed source areas were never declared free of Ae. aegypti.