Extant snake faunas have their origins in the mid-Cenozoic, when colubroids replaced booid-grade snakes as the dominant species. The timing of this faunal changeover in North America and Europe based on fossils is thought to have occurred in the early Neogene, after a period of global cooling opened environments and made them suitable for more active predators. However, new fossils from the late Oligocene of Tanzania have revealed an early colubroid-dominated fauna in Africa suggesting a different pattern of faunal turnover there. Additionally, molecular divergence times suggest colubroid diversification began sometime in the Paleogene, although the exact timing and driving forces behind the diversification are not clear. Here we present the first fossil snake referred to the African clade Lamprophiinae, and the oldest fossil known of Lamprophiidae. As such, this specimen provides the only potential fossil calibration point for the African snake radiation represented by Lamprophiidae, and is the oldest snake referred to Elapoidea. A molecular clock analysis using this and other previously reported fossils as calibration points reveals colubroid diversification minimally occurred in the earliest Paleogene, although a Cretaceous origin cannot be excluded. The elapoid and colubrid lineages diverged during the period of global warming near the Paleocene-Eocene boundary, with both clades diversifying beginning in the early Eocene (proximate to the Early Eocene Climate Optimum) and continuing into the cooler Miocene. The majority of subclades diverge well before the appearance of colubroid dominance in the fossil record. These results suggest an earlier diversification of colubroids than generally previously thought, with hypothesized origins of these clades in Asia and Africa where the fossil record is relatively poorly known. Further work in these regions may provide new insights into the timing of, and environmental influences contributing to, the rise of colubroid snakes.