The African genus Hyliota includes three or four species of warbler-like birds of uncertain phylogenetic affinities, as it has historically been placed in different avian families that are now known to represent unrelated lineages: Malaconotidae (bush-shrikes), Platysteiridae (batises and wattle-eyes), Muscicapidae (Old World flycatchers) and Sylviidae (Old-World Warblers). To assess the affinities of Hyliota we sequenced a mitochondrial protein-coding gene (ND2, 1018bp) and a nuclear intron (myoglobin intron-2, 685bp). Our analyses suggest that all previous hypotheses concerning the affinities of Hyliota are erroneous. Instead, Hyliota represents a basal branch in the Passerida radiation with no close relatives. Our results, which also include analyses of relationships among other of other atypical songbird genera, lend support to an African origin of the Passerida songbird radiation.