Chemical investigation of the psychrophilic fungus Pseudogymnoascus sp. HDN17-933 derived from Antarctica led to the discovery of six new tetrapeptides psegymamides A–F (1–6), whose planar structures were elucidated by extensive NMR and MS spectrometric analyses. Structurally, psegymamides D–F (4–6) possess unique backbones bearing a tetrahydropyridoindoles unit, which make them the first examples discovered in naturally occurring peptides. The absolute configurations of structures were unambiguously determined using solid-phase total synthesis assisted by Marfey’s method, and all compounds were evaluated for their inhibition of human (h) nicotinic acetylcholine receptor subtypes. Compound 2 showed significant inhibitory activity. A preliminary structure–activity relationship investigation revealed that the tryptophan residue and the C-terminal with methoxy group were important to the inhibitory activity. Further, the high binding affinity of compound 2 to hα4β2 was explained by molecular docking studies.