Humification plays an important role in stabilization of organic matter in soils of the cryolithic zone. In this context, the degree of organic matter stabilization has been assessed, using instrumental methods, for permafrost peat soils of the eastern European Arctic, based on selected plots from within the Komi Republic (Russian Federation). Humic substances (HSs) isolated from the mire permafrost peats of the forest-tundra subzone of the European Arctic have been characterized in terms of molecular composition. This was accomplished using elemental and amino acid fragments (AAFs) composition. Solid-state 13C nuclear magnetic resonance (13C NMR) spectroscopy was utilized to identify the structure of HSs. Changes in the molar x(H) : x(C) ratio, ratio of aromatic to paraffin fragments and ratio of hydroxy AAFs to heterocyclic AAFs along the peat profiles have been revealed. They are due to the activation of cryogenic processes in the upper part of the seasonally thawing layer, the natural selection of condensed humic molecules, the botanical composition and degree of degradation of peat, which reflect the climatic features of the area in the Holocene. Humic acids and fulvic acids of the peat soils showed the prevalence of compounds with a low degree of condensation and a low portion of aromatic fragments. The aromaticity degree showed the trend to increase within the depth. Changes of quantitative and qualitative parameters of specific organic compounds occur at the permafrost boundary of peatlands, which can serve as an indicator of recent climate changes in environments from the high latitudes. The presented data can be useful in the evaluation of soil organic matter stabilization degree in the active layer and below the permafrost table.