The genus Megaselia is one of the largest in the animal kingdom, with 1,600 described species and many more remaining to be discovered according to most experts. The biology is poorly known; some well-studied species have been shown to be parasitoids or extreme omnivores but it is suspected that larvae are mostly decomposers or fungivores. The genus can be found in most regions of the world but it is most diverse in the Holarctic, from temperate to arctic climates, at least judging from the described fauna. Work on Megaselia taxonomy is challenging due to the extreme species diversity, the poor knowledge of the higher-level phylogeny and the lack of molecular data. In this paper, we provide the first comprehensive study of Megaselia relationships based on molecular data. Although basal relationships in the genus remain uncertain, we identify 22 well-supported terminal clades, which we recognize as informal species groups. We briefly discuss the morphological characteristics of each species group, and the implications of our phylogenetic results for the genus-level classification of Megaselia and its closest relatives. We also provide molecular and brief morphological characterization of 45 Megaselia species new to science.