We examine the genetics, morphology and ecology of the widely distributed Megachile concinna species complex (Hymenoptera: Megachilidae), which is composed of numerous taxa of unclear taxonomic status in Africa and the Palearctic. In the Western Palearctic, three genetically distinct operational taxonomic units (OTUs) are found around the Mediterranean Sea: the western Mediterranean OTU M. pusilla, the eastern Mediterranean OTU M. anatolica and the predominantly Arabian OTU M. leucostoma. A morphological cline is present between anatolica and leucostoma in the Near East, despite a lack of mitochondrial introgression between the two; one nuclear marker suggests some gene flow between these OTUs. The contact zone between pusilla and leucostoma could not be sampled but phenotypic intergradation is also observed between these OTUs in northern Africa. In contrast, study of the contact zone between pusilla and anatolica indicates that both OTUs retain phenotypic and genomic integrity in sympatry over a contact zone spanning 1000 km. The arrangement of these three OTUs suggests a ring of interconnected populations around the Mediterranean Sea and sympatry between pusilla and anatolica at both ends of the ring in southeastern Europe. The latter two OTUs exhibit ecological differences, including phenology and host-plant preferences, which may contribute to their isolation. In addition, our results suggest that two OTUs, M. venusta and M. concinna, maintain genetic and phenotypic integrity in sympatry in parts of Africa; the latter is recognized as a valid species here. Lastly, our results indicate that two OTUs have been introduced independently into the New World, pusilla in North America and Argentina, and concinna in the Antilles.