The avian genus Saxicola is distributed throughout Africa, Asia, Europe and various islands across Oceania. Despite the fact that the group has great potential as a model to test evolutionary hypotheses due to the extensive variability in life history patterns recorded between and within species, the phylogenetic relationships among species and subspecies of this genus are poorly understood. We undertook a systematic investigation of the relationships within this genus with three main objectives in mind, (1) to test the monophyly of the genus; (2) to ascertain geographical origin and dispersal sequence; and (3) to test for monophyly within the most morphologically diverse species, S. torquata and S. caprata. We studied sequence data from the mitochondrial cytochrome b gene from 11 of the 12 recognized species and 15 of the 45 described subspecies. Four clades, two exclusively Asian, one Eurasian, and the fourth encompassing Eurasia and Africa, were identified. Based on our analyses, monophyly of the genus Saxicola is not supported and an Asian origin for the genus can be inferred. Results from DIVA analyses, tree topology and nodal age estimates suggest independent colonisation events from Asia to Africa and from Asia to the Western Palearctic, with the Sahara desert acting as a natural barrier for S. torquata. Subspecies and populations of S. torquata are not monophyletic due to S. tectes, S. dacotiae and S. leucura grouping within this complex. Subspecies and populations of S. caprata are monophyletic. Importantly, within S. torquata and S. caprata, slight morphological traits and plumage colour pattern differences used to recognize subspecies are indicative of the greater cryptic diversification that has occurred within this genus.