The relationship between body size and temperature of mammals is poorly resolved, especially for large keystone species such as bison (Bison bison). Bison are well-represented in the fossil record across North America, which provides an opportunity to relate body size to climate within a species. We measured the length of a leg bone (calcaneal tuber, DstL) in 849 specimens from 60 localities that were dated by stratigraphy and 14C decay. We estimated body mass (M) as: M = (DstL/11.49) 3. Average annual temperature was estimated from δ18O values in the ice cores from Greenland. Calcaneal tuber length of Bison declined over the last 40,000 years, that is, average body mass was 37% larger (910 ± 50 kg) than today (665 ± 21 kg). Average annual temperature has warmed by 6°C since the Last Glacial Maximum (~24-18 kya) and is predicted to further increase by 4°C by the end of the 21st century. If body size continues to linearly respond to global temperature, Bison body mass will likely decline by an additional 46%, to 357 ± 54 kg, with an increase of 4°C globally. The rate of mass loss is 41 ± 10 kg per °C increase of global temperature. Changes in body size of Bison may be a result of migration, disease, or human harvest but those effects are likely to be local and short-term and not likely to persist over the long-time-scale of the fossil record. The strong correspondence between body size of bison and air temperature is more likely the result of persistent effects on the ability to grow and the consequences of sustaining a large body mass in a warming environment. Continuing rises in global temperature will likely depress body sizes of bison, and perhaps other large grazers, without human intervention.