The dogma of strict maternal inheritance of mitochondria is now being tested with population genetics methods on sequence data from many species. In this study we investigated whether recombination occurs in the mitochondria of the blue tit (Parus caeruleus) by studying polymorphisms in the mitochondrial control region and in a recently identified (A)n microsatellite on the W chromosome. The female heterogamety of avian sex chromosomes allows a test of whether mitochondrial recombination affects genealogical inference by comparison of mitochondrial and W-linked sequence variation. There is no discrepancy between mitochondrial and W-linked genealogies in blue tits, consistent with no recombination. We also analyzed mitochondrial sequence variation in both blue tits and peregrine falcons (Falco peregrinus) using a coalescent-based approach which accounts for recurrent mutation; in neither bird species did we find evidence of recombination. We conclude that it is unlikely that mitochondrial recombination has large effects on mitochondrial genetic variability in birds.