Fleas (order Siphonaptera) are highly-specialized, diverse blood-feeding ectoparasites of mammals and birds with an enigmatic evolutionary history and obscure origin. We here present a molecular phylogenetic study based on a comprehensive taxon sampling of 259 flea taxa, representing 16 of the 18 extant families of this order. A Bayesian phylogenetic tree with strong nodal support was recovered, consisting of seven sequentially derived lineages with Macropsyllidae as the earliest divergence, followed by Stephanocircidae. Divergence times of flea lineages were estimated based on fossil records and host specific associations to bats (Chiroptera), suggesting that the common ancestor of extant Siphonaptera diversified during the Cretaceous. However, most of the intraordinal divergence into extant lineages took place after the K-Pg boundary. Ancestral states of host association and biogeographical distribution were reconstructed, suggesting with high likelihood that fleas originated in the southern continents (Gondwana) and migrated from South America to their extant distributions in a relatively short time frame. Theria (placental mammals and marsupials) represent the most likely ancestral host group of extant Siphonaptera, with marsupials occupying a more important role than previously assumed. Major extant flea families evolved in connection to post K-Pg diversification of Placentalia. The association of fleas with monotremes and birds is likely due to later secondary host association. These results suggest caution in casually interpreting recently discovered Mesozoic fossil ?dinosaur fleas? of Northeast Asia as part of what we currently consider Siphonaptera.