Drosophila melanogaster is widely used as a model in DNA variation studies. Patterns of polymorphism have, however, been affected by the history of this species, which is thought to have recently spread out of Africa to the rest of the world. We analyzed DNA sequence variation in 11 populations, including four continental African and seven non-African samples (including Madagascar), at four independent X-linked loci. Variation patterns at all four loci followed neutral expectations in all African populations, but departed from it in all non-African ones due to a marked haplotype dimorphism at three out of four loci. We also found that all non-African populations show the same major haplotypes, though in various frequencies. A parsimonious explanation for these observations is that all non-African populations are derived from a single ancestral population having undergone a substantial reduction of polymorphism, probably through a bottleneck. Less likely alternatives involve either selection at all four loci simultaneously (including balancing selection at three of them), or admixture between two divergent populations. Small but significant structure was observed among African populations, and there were indications of differentiation across Eurasia for non-African ones. Since population history may result in non-equilibrium variation patterns, our study confirms that the search for footprints of selection in the D. melanogaster genome must include a sufficient understanding of its history.