The size of plant stomata (adjustable pores that determine the uptake of CO₂ and loss of water from leaves) is considered to be evolutionarily important. This study uses fossils from the major Southern Hemisphere family Proteaceae to test whether stomatal cell size responded to Cenozoic climate change. We measured the length and abundance of guard cells (the cells forming stomata), the area of epidermal pavement cells, stomatal index and maximum stomatal conductance from a comprehensive sample of fossil cuticles of Proteaceae, and extracted published estimates of past temperature and atmospheric CO₂. We developed a novel test based on stochastic modelling of trait evolution to test correlations among traits. Guard cell length increased, and stomatal density decreased significantly with decreasing palaeotemperature. However, contrary to expectations, stomata tended to be smaller and more densely packed at higher atmospheric CO₂. Thus, associations between stomatal traits and palaeoclimate over the last 70 million years in Proteaceae suggest that stomatal size is significantly affected by environmental factors other than atmospheric CO₂. Guard cell length, pavement cell area, stomatal density and stomatal index covaried in ways consistent with coordinated development of leaf tissues.