The Rancho La Brea Tar Pits is the world's richest and most important Late Pleistocene fossil locality and best renowned for numerous fossil mammals and birds excavated over the past century. Less researched are insects, even though these specimens frequently serve as the most valuable paleoenvironemental indicators due to their narrow climate restrictions and life cycles. Our goal was to examine fossil material that included insect-plant associations, and thus an even higher potential for significant paleoenviromental data. Micro-CT scans of two exceptionally preserved leafcutter bee nest cells from the Rancho La Brea Tar Pits in Los Angeles, California reveal intact pupae dated between ∼23,000-40,000 radiocarbon years BP. Here identified as best matched to Megachile (Litomegachile) gentilis Cresson (Hymenoptera: Megachilidae) based on environmental niche models as well as morphometrics, the nest cells (LACMRLP 388E) document rare preservation and life-stage. The result of complex plant-insect interactions, they offer new insights into the environment of the Late Pleistocene in southern California. The remarkable preservation of the nest cells suggests they were assembled and nested in the ground where they were excavated. The four different types of dicotyledonous leaves used to construct the cells were likely collected in close proximity to the nest and infer a wooded or riparian habitat with sufficient pollen sources for larval provisions. LACMRLP 388E is the first record of fossil Megachile Latreille cells with pupae. Consequently, it provides a pre-modern age location for a Nearctic group, whose phylogenetic relationships and biogeographic history remain poorly understood. Megachile gentilis appears to respond to climate change as it has expanded its distribution across elevation gradients over time as estimated by habitat suitability comparisons between low and high elevations; it currently inhabits mesic habitats which occurred at a lower elevation during the Last Glacial Maximum ∼21,000 years ago. Nevertheless, the broad ecological niche of M. gentilis appears to have remained stable.