The avian genus Calandrella (larks) was recently suggested to be non-monophyletic, and was divided into two genera, of which Calandrella sensu stricto comprises 4–5 species in Eurasia and Africa. We analysed mitochondrial cytochrome b (cytb) and nuclear Restriction-site Associated DNA (RAD) sequences from all species, and for cytb we studied 21 of the 22 recognised subspecies, with the aim to clarify the phylogenetic relationships within the genus and to compare large-scale nuclear sequence patterns with a widely used mitochondrial marker. Cytb indicated deep splits among the currently recognised species, although it failed to support the interrelationships among most of these. It also revealed unexpected deep divergences within C. brachydactyla, C. blanfordi/C. erlangeri, C. cinerea, and C. acutirostris. It also suggested that both C. brachydactyla and C. blanfordi, as presently circumscribed, are paraphyletic. In contrast, most of the many subspecies of C. brachydactyla and C. cinerea were unsupported by cytb, although two populations of C. cinerea were found to be genetically distinct. The RAD data corroborated the cytb tree (for the smaller number of taxa analysed) and recovered strongly supported interspecific relationships. However, coalescence analyses of the RAD data, analysed in SNAPP both with and without an outgroup, received equally strong support for two conflicting topologies. We suggest that the tree rooted with an outgroup – which is not recommended for SNAPP – is more trustworthy, and suggest that the reliability of analyses performed without any outgroup species should be thoroughly evaluated. We also demonstrate that degraded museum samples can be phylogenetically informative in RAD analyses following careful bioinformatic treatment. We note that the genus Calandrella is in need of taxonomic revision.