The involvement of DNA methylation in the response to cold stress of two different yeast species (Naganishia antarctica, psychrophilic, and Naganishia albida, psychrotolerant), exhibiting different temperature aptitudes, has been studied. Consecutive incubations at respective optimum temperatures, at 4 °C (cold stress) and at optimum temperatures again, were performed. After Methylation Sensitive Amplified Polymorphism (MSAP) fingerprints a total of 550 and 423 clear and reproducible fragments were amplified from N. antarctica and N. albida strains, respectively. The two Naganishia strains showed a different response in terms of level of DNA methylation during cold stress and recovery from cold stress. The percentage of total methylated fragments in psychrophilic N. antarctica did not show any significant change. On the contrary, the methylation of psychrotolerant N. albida exhibited a nonsignificant increase during the incubation at 4 °C and continued during the recovery step, showing a significant difference if compared with control condition, resembling an uncontrolled response to cold stress. A total of 12 polymorphic fragments were selected, cloned, and sequenced. Four fragments were associated to genes encoding for elongation factor G and for chitin synthase export chaperon. To the best of our knowledge, this is the first study on DNA methylation in the response to cold stress carried out by comparing a psychrophilic and a psychrotolerant yeast species.