Palaeotemperature reconstructions are valuable palaeoclimate indicators and important tools for the understanding of interactions in the climate system. They form a basis for models identifying the impact of various processes within the past and future climate system. Siberia is a region with large organic carbon reserves stored in permafrost (perennially frozen ground). Temperatures in this region are thus important as a driver for a positive feedback to the global climate. Local temperature histories in the ice-rich permafrost areas of the Russian Arctic are either sparse or based on proxy data with potential seasonal biases. Borehole temperature reconstructions are sensitive to the temperature signal throughout the year and available in regions for which no other records exist. This study used two inversion methods, particle swarm optimization and a least squares technique, to retrieve temperature histories of the last 200-300 years in the Laptev Sea region from two permafrost borehole temperature records. The retrieved histories were compared to larger scale reconstructions from the region. Distinct differences in the histories between the Lena Delta and western Laptev Sea sites were found, notably a one-century delay of warming and a three decade delay in peak warming in the western Laptev Sea. The local permafrost surface temperatures at Sardakh Island (central Lena Delta) resembled the circum-Arctic regional average trends. At Mamontov Klyk (western Laptev Sea) this was the case only for the most recent decade. In contrast, the Mamontov Klyk history was more similar to northern hemispheric mean trends. A rapid recent warming of synoptic scale was consistently observed at both sites. Differences in the past temperature trends between the sites may be caused by regionally differing environmental influences, such as atmospheric circulation and sea ice coverage. The re-constructed magnitude of temperature changes is consistent with warming greater than mean Arctic temperature trends. In conclusion, reconstruction from shallow permafrost boreholes provides short-scale temperature histories in the coastal tundra of the remote Arctic (resolved at annual to multi-decadal scale). As local differences from the circum-Arctic average – including later warming and higher warming magnitude – were shown to exist in this region, our results provide a basis for local surface temperature record parameterization of climate models and of permafrost models in particular-