In central Siberia, past temperature changes have been driving permafrost warming in a region with large organic carbon reserves stored in the perennially frozen ground. However, local arctic temperature histories in the ice-rich permafrost areas of the remote Russian Arctic are sparsely known or based on proxy data with potential seasonal biases and underrepresented in circum-Arctic reconstructions. This study employed two inversion schemes (particle swarm optimization and a least-square method) to reconstruct temperature histories for the past 200–300 years in the Laptev Sea region from two permafrost borehole temperature records. These data were evaluated against larger scale reconstructions from the region. Distinct differences between the western Laptev Sea and the Lena Delta sites were recognized, such as a transition to warmer temperatures a century later in the western Laptev Sea as well as a peak in warming 3 decades later. The local permafrost surface temperature history at Sardakh Island in the Lena Delta was reminiscent of the circum-Arctic regional average trends. However, Mamontov Klyk in the western Laptev Sea was consistent to Arctic trends only in the most recent decade and was more similar to northern hemispheric mean trends. Both sites are consistent with a rapid recent warming that is of synoptic scale. Different environmental influences such as synoptic atmospheric circulation and sea ice may be responsible for differences between the sites. The shallow permafrost boreholes provide missing well-resolved short-scale temperature information in the coastal permafrost tundra of the Arctic. As local differences from circum-Arctic reconstructions, such as 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 in particular of permafrost models.