Leaf warblers (Aves; Phylloscopidae) are a diverse clade of insectivorous, canopy-dwelling songbirds widespread across the Old World. The taxonomy of Australasian leaf warblers is particularly complex, with multiple species-level divergences between island taxa in the region requiring further scrutiny. We use a combination of morphology, bioacoustics, and analysis of thousands of genome-wide markers to investigate and describe a new species of Phylloscopus leaf warbler from the island of Rote in the Lesser Sundas, Indonesia. We show that this new Rote Leaf Warbler is morphologically and genomically highly distinct from its congenerics, but do not find vocal differentiation between different island taxa. We discuss the behaviour and ecology of this highly distinctive new species, and make recommendations about its conservation status. We believe this constitutes the first description of a novel bird species that is partly based on insights from massive amounts of genome-wide DNA markers.