We reconstruct a comprehensively sampled molecular phylogeny for the second most species-rich tribe of the ladybird beetle family Coccinellidae, the charismatic Coccinellini. We analysed a dataset consisting of five nuclear and three mitochondrial gene fragments from 150 taxa to provide a detailed phylogeny and estimates of historical divergence times using Bayesian relaxed clocks and primary fossil calibrations and an assessment of the evolution of feeding habits. The results of phylogenetic analyses provide strong support for the monophyly of the tribe Coccinellini, highlight the existence of four major clades and most sampled Coccinellini genera (30 out of 34) were recovered monophyletic. Our dating analyses suggest an Early Cretaceous origin for Coccinellidae at ca. 140 millions years ago (Ma) and a Late Cretaceous origin for the tribe Coccinellini at ca. 83.8 Ma. Ancestral character state estimation of feeding habits highlights a high level of phylogenetic niche conservatism on aphids and indicates that the most common recent ancestor of Coccinellini likely also fed on aphids. Our reconstruction of feeding habits and assessment of the aphid fossil record suggests that the diversification of Coccinellini paralleled that of Aphididae, although with substantial variation in host-breadth and the tendency for a few specialized lineages towards non-aphid feeding.