Present-day temperature profile may be used as an important constraint for reconstruction of the thermal regime in sedimentary basin modeling. This type of profile is significantly non-steady state, especially for basins located at high and middle latitudes. However, estimations of past thermal regimes are indefinite and often limited by knowledge of past glaciations and by the simple two-layer model usually employed. In this paper, permafrost modeling was carried out as a continuation of basin modeling of the sedimentary section of Urengoy field of the West Siberian basin (66°N, 77°E). Consideration of surface temperatures beginning with the Triassic, a refined initial temperature distribution, permafrost modeling for the past 3.4 Ma, and use of a real lithological cross section distinguish this approach from previous studies. Depth and time variations in thermophysical parameters of rocks (heat conductivity, heat capacity, unfrozen water content, salt content, and porosity) had a considerable influence on the results of modeling. The time 3.4 Ma, when air temperatures in the area became lower than 0 °C, has been considered as the initial time for permafrost modeling. According to the model, initial temperatures deviated 10–15 °C from their present-day values due to climate variations during the last 3.4 Ma. Deviations in the value of heat flow can exceed 100%. There were about five glacial periods in the Late Pliocene and nearly the same number in the Pleistocene in the area. The estimated thickness of permafrost did not exceed 650 m and the depth of the lower boundary of methane hydrate stability did not exceed 900 m (from the ground surface). Today, the predicted depths of permafrost and of hydrate stability (from 250 to 700 m) are in reasonable agreement with the observed values for the Urengoy area.