An observational, exploratory, cross-sectional study was performed to assess whether the presence of atypical naevi (AN) in adolescents is associated with psychological and psychovegetative stress parameters. Fifty-one students of a secondary school in Graz, Austria, completed a defined test procedure consisting of an initial period of rest, a standardised mental stress task, another period rest and a questionnaire, the change-sensitive symptom list (ASS-SYM). Electrocardiogram and blood pressure were recorded continuously. The study population was divided in two groups: probands without AN (NAN, n = 33), and probands with at least one AN (n = 18). We found higher values for the AN group in all scales of ASS-SYM, reaching statistical significance in the dimensions "nervousness and mental tension" (p = 0.025), "psychophysiological dysregulation" (p = 0.020), burden of pain" (p = 0.023) and "general symptoms and problems" (p = 0.031). Regarding physiological parameters, the AN group showed higher vegetative strain reflected in heart rate and heart rate varibility during the periods of rest as well as a reduced baroreceptor sensitivity. On the basis of our results, the presence of AN in adolescents seems to be associated with a higher vegetative arousal. Additionally, participants with AN complained significantly more often about stress-associated general psychological symptoms and problems.