Positive selection on a new beneficial mutation generates a characteristic pattern of DNA sequence polymorphism when it reaches an intermediate allele frequency. On genome sequences of African Drosophila melanogaster, we detected such signatures of selection at 37 candidate loci and identified “sweeping haplotypes (SHs)” that are increasing or have increased rapidly in frequency due to hitchhiking. Based on geographic distribution of SH frequencies, we could infer whether selective sweeps occurred starting from de novo beneficial mutants under simple constant selective pressure. Single SHs were identified at more than half of loci. However, at many other loci, we observed multiple independent SHs, implying soft selective sweeps due to a high beneficial mutation rate or parallel evolution across space. Interestingly, SH frequencies were intermediate across multiple populations at about a quarter of the loci despite relatively low migration rates inferred between African populations. This invokes a certain form of frequency-dependent selection such as heterozygote advantage. At one locus, we observed a complex pattern of multiple independent that was compatible with recurrent frequency-dependent positive selection on new variants. In conclusion, genomic patterns of positive selection are very diverse, with equal contributions of hard and soft sweeps and a surprisingly large proportion of frequency-dependent selection in D. melanogaster populations.