The avian family Paridae (tits and chickadees) contains c. 55 species distributed in the Palearctic, Nearctic, Afrotropic and Indomalaya. The group includes some of the most well-known and extensively studied avian species, and the evolutionary history, in particular the post-glacial colonization of the northern latitudes, has been comparably well-studied for several species. Yet a comprehensive phylogeny of the whole clade is lacking. Here, we present the first complete species phylogeny for the group based on sequence data from two nuclear introns and one mitochondrial gene for 67 taxa of Paridae. Our results strongly support the inclusion of the Fire-capped Tit (Cephalopyrus flammiceps), currently placed in the Remizidae, as the most basal member of the Paridae. The Yellow-browed Tit (Sylviparus modestus) and the Sultan Tit (Melanochlora sultanea) constitute the next two sequential branches whereas the remaining tits falls into two large clades, one of which contains the seed hoarding and nest excavating species. The indicated clades within these two groups are largely congruent with recent classifications, with several unforeseen relationships, such as non-monophyly of the Sombre Tit (Poecile lugubris) and the Marsh Tit (Poecile palustris), as well as non-monophyly of both the African grey and the African black tits. Further, our results support a close relationship between the White-fronted Tit (Parus semilarvatus) and the varied Tit (Poecile varius) as well as a close relationship between the White-naped Tit (Parus nuchalis) and the Yellow-cheecked and Black-lored tits (Parus spilonotus and P. xanthogenys). We propose a new classification that is in accordance with this phylogeny.