Abstract Arctic sea ice decline in recent decades has been dramatic; however, few long-term records of Arctic sea ice exist to put such a decline in context. Here we employ an ensemble Kalman filter data assimilation approach to reconstruct Arctic sea ice concentration over the last two millennia by assimilating temperature-sensitive proxy records with ensembles drawn from last millennium climate model simulations. We first test the efficacy of this method using pseudoproxy experiments. Results show good agreement between the target and reconstructed total Arctic sea ice extent (R2 value and coefficient of efficiency values of 0.51 and 0.47 for perfect model experiments and 0.43 and 0.43 for imperfect model experiments). Imperfect model experiments indicate that the reconstructions inherit some bias from the model prior. We assimilate 487 temperature-sensitive proxy records with two climate model simulations to produce two gridded reconstructions of Arctic sea ice over the last two millennia. These reconstructions show good agreement with satellite observations between 1979 and 1999 CE for total Arctic sea ice extent with an R2 value and coefficient of efficiency of about 0.60 and 0.50, respectively, for both models. Regional quantities derived from these reconstructions show encouraging similarities with independent reconstructions and sea ice sensitive proxy records from the Barents Sea, Baffin Bay, and East Greenland Sea. The reconstructions show a positive trend in Arctic sea ice extent between around 750 and 1820 CE, and increases during years with large volcanic eruptions that persist for about 5 years. Trend analysis of total Arctic sea ice extent reveals that for time periods longer than 30 years, the satellite era decline in total Arctic sea ice extent is unprecedented over the last millennium. Significance Statement Areal coverage of Arctic sea ice is a critical aspect of the climate system that has been changing rapidly in recent decades. Prior to the advent of satellite observations, sparse observations of Arctic sea ice make it difficult to put the current changes in context. Here we reconstruct annual averages of Arctic sea ice coverage for the last two millennia by combining temperature-sensitive proxy records (i.e., ice cores, tree rings, and corals) with climate model simulations using a statistical technique called data assimilation. We find large interannual changes in Arctic sea ice coverage prior to 1850 that are associated with volcanic eruptions, with a steady rise in Arctic sea ice coverage between 750 and 1820 CE. The satellite-period loss of sea ice has no analog during the last millennium.