Since the Arctic Ocean began forming in the Early Cretaceous 112-140 million years ago, the Arctic region has undergone profound oceanographic and paleoclimatic changes. It has evolved from a warm epicontinental sea to its modern state as a cold isolated ocean with extensive perennial sea ice cover. Our understanding of the long-term paleoclimate evolution of the Arctic remains fragmentary but has advanced dramatically in the past decade through analysis of new marine and terrestrial records, supplemented by important insights from paleoclimate models. Improved understanding of how these observations fit into the long-term evolution of the global climate system requires additional scientific drilling in the Arctic to provide detailed and continuous paleoclimate records, and to resolve the timing and impact of key tectonic and physiographic changes to the ocean basin and surrounding landmasses. Here, we outline the long-term paleoclimatic evolution of the Arctic, with a focus on integrating both terrestrial and marine records.