In China, gas hydrates in onshore permafrost areas have so far only been found in the Juhugeng Mine of the Qilian Mountains. However, their subsurface distribution remains unclear. Electrical resistivity logs have revealed that zones containing gas hydrates have higher resistivity than surrounding zones, which makes electromagnetic methods viable for detecting gas-hydrate deposits. We have deployed a natural-source audio-magnetotelluric (AMT) survey at the Juhugeng Mine. AMT data were collected at 176 sites along five profiles, and resistivity models were derived from 2D inversions after detailed data analysis. After the available geologic and geophysical observations were combined, the inversion results from profile 1 suggested that permafrost near the surface with high resistivity and thickness is essential for underlying gas hydrates to be present. The decrease in resistivity and/or thickness of permafrost due to climate change may lead to gas-hydrate dissociation. The other four AMT transects suggested three prospective gas-hydrate sites. Our results indicate that the AMT survey technique is suitable for exploring gas hydrates in permafrost areas and analyzing the impact of permafrost characteristics on gas-hydrate occurrence.