In this work the authors considered a freezing-and-melting process of soils under the polyurethaneinsulated polyethylene heating pipeline, which is used in the regions with permafrost soils. Temperature field dynamics of the “pipeline – soil” system is determined by heat conductivity equation in polar coordinate system. The corresponding two-dimensional Stefan problem is solved by the finite differences method. The authors propose to determine the thickness of pipeline thermal insulation and the embedment depth upon the condition of melting depth reduction to an annual thawed layer of soil identified before the heating season. There are presented results of isotherm calculations for underground heat supply pipelines interacting with frozen soil. These results show that reduction of melting depth to annual thawed layer is probable. The calculations were carried out for simulated soil and temperature conditions of Yakutsk, Republic Sakha, Russia. Nevertheless, the results obtained can be applied in other permafrost areas.