Frozen ground plays an important role in the energy and water cycle of cold regions, and affects the environment and agricultural practices in these regions. The effect of climate warming on soil frost is an important concern, but our present understanding of such effect is limited, due to the lack of long-term data covering a large region. This study analyzes a unique regional database of 20-year records from 1986-2005 of soil frost, combined with long-term climate data from 1955-2005. Annual maximum frost depths (D_max) in the Township of Memuro (514 km²) in Tokachi, Hokkaido have decreased significantly in the last 20 years. The decrease in D_max was caused by the development of thick snow cover in early winter that insulates the ground, not by the increase in air temperature. The D_max is strongly correlated with a soil freezing index (F₂₀), that integrates the combined effects of air temperature and snow cover. Using F₂₀ as a surrogate of D_max, it was shown that the decreasing frost depth was a regional phenomenon occurring over the Tokachi Plain, covering an area of several thousand square kilometers. The timing of a major decrease in F₂₀ in the mid to late 1980’s coincided with sharp decreases of snowfall in the Hokuriku region of Japan and the amount of drift ice in the southern part of the Sea of Okhotsk, both of which are regarded as indicators of the strength of the East Asian winter monsoon activities.