Molecular variation is often used to infer the demographic history of species, but sometimes the complexity of species history can make such inference difficult. The willow warbler, Phylloscopus trochilus, shows substantially less geographical variation than the chiffchaff, Phylloscopus collybita, both in morphology and in mitochondrial DNA (mtDNA) divergence. We therefore predicted that the willow warbler should harbour less nuclear DNA diversity than the chiffchaff. We analysed sequence data obtained from multiple samples of willow warblers and chiffchaffs for the mtDNA cytochrome b gene and four nuclear genes. We confirmed that the mtDNA diversity among willow warblers is low (π = 0.0021). Sequence data from three nuclear genes (CHD-Z, AFLP-WW1 and MC1R) not linked to the mitochondria demonstrated unexpectedly high nucleotide diversity (π values of 0.0172, 0.0141 and 0.0038) in the willow warbler, on average higher than the nucleotide diversity for the chiffchaff (π values of 0.0025, 0.0017 and 0.0139). In willow warblers, Tajima's D analyses showed that the mtDNA diversity, but not the nuclear DNA diversity, has been reduced relative to the neutral expectation of molecular evolution, suggesting the action of a selective sweep affecting the maternally inherited genes. The large nuclear diversity seen within willow warblers is not compatible with processes of neutral evolution occurring in a population with a constant population size, unless the long-term effective population size has been very large (Ne > 106). We suggest that the contrasting patterns of genetic diversity in the willow warbler may reflect a more complex evolutionary history, possibly including historical demographic fluctuations or historical male-biased introgression of nuclear genes from a differentiated population of Phylloscopus warblers.