A time series of temperature measurements in permafrost in the Eastern part of Russia were made for depths up to 30 m. During the data processing, we have observed a rhythmic variability of mean annual temperatures with periods of 9-13 and about 40 years, that correspond with the well-known cycles of Wolf and Bruckner. We have discovered stable correlations between temperature oscillations and solar activity variations with a significance level of 1-5%. We have computed regression equations which help us to predict the permafrost thermal changes for a 5-11-year period with a maximum error less than 0.2 degrees C. These investigations show that permafrost temperature oscillations over an extended period are probably controlled by sun-spot cycles. In this work we have confined ourselves to show only the main results in this direction and left discussion of general inferences for other articles which are in preparation.