Malaria endemicity in Southwest Iberia afforded conditions for an increase of sickle cell disease (SCD), which in the region follows a clinal pattern toward the south, where foci of high prevalence were found. SCD distribution is associated with specific geographical areas, and therefore, its introduction into Iberia may be related to the migration of different populations. We have analyzed the variation of uniparental markers in Portuguese populations with high frequency of SCD--Coruche, Pias, and Alcacer do Sal--to evaluate if their present-day pattern of neutral diversity could provide evidence about people inhabiting the area over different time periods. Two hundred and eighty-five individuals were sampled in Coruche, Pias, and Alcacer do Sal. All were analyzed for the control region of mitochondrial DNA (mtDNA); males were additionally examined for Y-chromosome markers. Results were then compared with data from other Portuguese and non-Portuguese populations. In Coruche, the genetic profile was similar to the profile usually found in Portugal. In Alcacer do Sal, the frequency of sub-Saharan mtDNA L lineages was the highest ever reported (22%) in Europe. In Pias, mtDNA diversity revealed higher frequencies of Mediterranean haplogroups I, J, and T than usually found in surrounding populations. The presence of Sub-Saharan maternal lineages in Alcacer do Sal is likely associated with the influx of African slaves between the 15th and 19th centuries, whereas in Pias, the Mediterranean influence might be traced to ancient contacts with Greeks, Phoenicians, and Carthaginians, who established important trading networks in southern Iberia.