The temperature history of the first millennium C.E. is sparsely documented, especially in the Arctic. We present a synthesis of decadally resolved proxy temperature records from poleward of 60 degrees N covering the past 2000 years, which indicates that a pervasive cooling in progress 2000 years ago continued through the Middle Ages and into the Little Ice Age. A 2000-year transient climate simulation with the Community Climate System Model shows the same temperature sensitivity to changes in insolation as does our proxy reconstruction, supporting the inference that this long-term trend was caused by the steady orbitally driven reduction in summer insolation. The cooling trend was reversed during the 20th century, with four of the five warmest decades of our 2000-year-long reconstruction occurring between 1950 and 2000.