The phylogenetic relationships of the Blue Tit-Azure Tit assemblage (genus Parus; Aves: Passeriformes) were studied using mitochondrial DNA sequences of 24 specimens representing seven subspecies from Eurasia and North Africa. Previous work based on comparative morphological and acoustic data suggested a division of the Blue Tit (Parus caeruleus) into two species. Our analyses clearly indicate that the Blue Tit represents a paraphyletic assemblage, including a European/Middle Asian clade that is the sister group to the Azure Tit (Parus cyanus) and a North African clade. The North African clade (teneriffae subspecies group) is a sister group to the European Blue Tit/Azure Tit clade. We suggest a division of the Blue Tit into two separate species, Eurasian Blue Tit (Parus caeruleus s. str.) and African Blue Tit (Parus teneriffae). However, our data give no support for assigning species rank to Parus cyanus flavipectus, a subspecies of the Azure Tit, as suggested by several authors on morphological grounds.