Background: Nutritional beliefs play an important role when it comes to food choice. However, little attention has been paid to which foods individuals believe to be comforting when experiencing stress. With increasing health awareness in the general public, this study aims to examine whether the nutritional belief exists that only healthy foods relieve stress. If so, we are interested in its relationship to Orthorexia Nervosa (ON) tendencies. Methods: 175 participants (mean age 28.5 ± 7.8 years, 124 females) completed questionnaires to assess beliefs about stress-relieving foods and ON tendencies. Principal component analysis was used to reduce foods to food groups. Subsequently, a latent profile analysis was performed to identify groups with distinct nutritional beliefs. Results: Among eight distinct groups, one group (8% of the sample) reported the belief that exclusively healthy foods relieve stress. Multinominal logistic regressions showed that higher ON tendencies were associated with that group. Conclusions: Our findings suggest that individuals with stronger ON tendencies believe that, in particular, healthy foods relieve stress. This indicates that nutritional beliefs in ON concern not only the somatic consequences of certain foods, but also psychological consequences, which might also drive orthorexic behaviour. This offers a new target for the diagnosis and treatment of ON.