Most evidence of climate change impacts on food webs comes from modern studies and little is known about how ancient food webs have responded to climate changes in the past. Here, we integrate fossil evidence from 71 fossil sites, body-size relationships and actualism to reconstruct food webs for six large mammal communities that inhabited the Iberian Peninsula at different times during the Quaternary. We quantify the long-term dynamics of these food webs and study how their structure changed across the Quaternary, a period for which fossil data and climate changes are well known. Extinction, immigration and turnover rates were correlated with climate changes in the last 850 kyr. Yet, we find differences in the dynamics and structural properties of Pleistocene versus Holocene mammal communities that are not associated with glacial-interglacial cycles. Although all Quaternary mammal food webs were highly nested and robust to secondary extinctions, general food web properties changed in the Holocene. These results highlight the ability of communities to re-organize with the arrival of phylogenetically similar species without major structural changes, and the impact of climate change and super-generalist species (humans) on Iberian Holocene mammal communities.