Using the climate model CLIMBER-X, we present an efficient method for assimilating the temporal evolution of surface temperatures for the last deglaciation covering the period 22000 to 6500 years before the present. The data assimilation methodology combines the data and the underlying dynamical principles governing the climate system to provide a state estimate of the system, which is better than that which could be obtained using just the data or the model alone. In applying an ensemble Kalman filter approach, we make use of the advances in the parallel data assimilation framework (PDAF), which provides parallel data assimilation functionality with a relatively small increase in computation time. We find that the data assimilation solution depends strongly on the background evolution of the decaying ice sheets rather than the assimilated temperatures. Two different ice sheet reconstructions result in a different deglacial meltwater history, affecting the large-scale ocean circulation and, consequently, the surface temperature. We find that the influence of data assimilation is more pronounced on regional scales than on the global mean. In particular, data assimilation has a stronger effect during millennial warming and cooling phases, such as the Bølling-Allerød and Younger Dryas, especially at high latitudes with heterogeneous temperature patterns. Our approach is a step toward a comprehensive paleo-reanalysis on multi-millennial time scales, including incorporating available paleoclimate data and accounting for their uncertainties in representing regional climates.