The deep divergence between the African endemic passerines Picathartidae (rockfowl Picathartes and rockjumpers Chaetops, four species) and the Passerida (ca. 3500 species) suggests an older history of oscines on the African continent than has previously been assumed. In order to determine whether any additional, unexpectedly deep lineages occur in African endemic songbirds, 29 species--including 10 enigmatic focal taxa endemic to southern Africa--were added to a large nuclear sequence dataset gathered from oscine songbirds (Passeri). Phylogenetic analyses of these data resolve many long-standing questions about the affinities of these birds, not all of which were predicted by traditional approaches. The application of a molecular clock indicates that most basal divergences in Passerida occurred in the middle to late Eocene, with divergences between African and Australasian core corvoids occurring somewhat later in the early Miocene. Consistent with inferences for mammals, divergences between Malagasy endemic passerines and their mainland relatives suggests an asynchronous colonization history. This emerging phylogenetic picture reveals that relationships within Old World families are highly informative regarding the early dispersal and radiation of songbirds out of Gondwana. Future analyses will depend on improving resolution of higher-level phylogenetic relationships among these groups, and increasing the density of taxon sampling within them.