We report a time-calibrated stratigraphic section in Colorado that contains unusually complete fossils of mammals, reptiles, and plants and elucidates the drivers and tempo of biotic recovery during the poorly known first million years after the Cretaceous-Paleogene mass extinction (KPgE). Within ~100 thousand years (ka) post-KPgE, mammalian taxonomic richness doubled, and maximum mammalian body mass increased to near pre-KPgE levels. A threefold increase in maximum mammalian body mass and dietary niche specialization occurred at ~300 ka post-KPgE, concomitant with increased megafloral standing species richness. The appearance of additional large mammals occurred by ~700 ka post-KPgE, coincident with the first appearance of Leguminosae (the bean family). These concurrent plant and mammal originations and body-mass shifts coincide with warming intervals, suggesting that climate influenced post-KPgE biotic recovery.