Pollution of the Arctic Ocean by potentially toxic elements (PTEs) is a current environmental problem. Humic acids (HAs) play an important role in the regulation of PTE mobility in soil and water. The permafrost thaw releases ancient organic matter (OM) with a specific molecular composition into the Arctic watersheds. This could affect the mobility of PTEs in the region. In our study, we isolated HAs from two types of permafrost deposits: the Yedoma ice complex, which contains pristine buried OM, and the alas formed in the course of multiple thaw–refreezing cycles with the most altered OM. We also used peat from the non-permafrost region as the recent environmental endmember for the evolution of Arctic OM. The HAs were characterized using 13C NMR and elemental analysis. Adsorption experiments were conducted to assess the affinity of HAs for binding Cu2+ and Ni2+. It was found that Yedoma HAs were enriched with aliphatic and N-containing structures as compared to the much more aromatic and oxidized alas and peat HAs. The adsorption experiments have revealed that the peat and alas HAs have a higher affinity for binding both ions as compared to the Yedoma HAs. The obtained data suggest that a substantial release of the OM from the Yedoma deposits due to a rapid thaw of the permafrost might increase the mobility of PTEs and their toxicity in the Arctic Ocean because of much lesser “neutralization potential”.