INTRODUCTION: Better mental health has been associated with exposure to natural outdoor environments (NOE). However, comprehensive studies including several indicators of exposure and outcomes, potential effect modifiers and mediators are scarce. OBJECTIVES: We used novel, objective measures to explore the relationships between exposure to NOE (i.e. residential availability and contact) and different indicators of mental health, and possible modifiers and mediators. METHODS: A nested cross-sectional study was conducted in: Barcelona, Spain; Stoke-on-Trent, United Kingdom; Doetinchem, Netherlands; Kaunas, Lithuania. Participants' exposure to NOE (including both surrounding greenness and green and/or blue spaces) was measured in terms of (a) amount in their residential environment (using Geographical Information Systems) and (b) their contact with NOE (using smartphone data collected over seven days). Self-reported information was collected for mental health (psychological wellbeing, sleep quality, vitality, and somatisation), and potential effect modifiers (gender, age, education level, and city) and mediators (perceived stress and social contacts), with additional objective NOE physical activity (potential mediator) derived from smartphone accelerometers. RESULTS: Analysis of data from 406 participants showed no statistically significant associations linking mental health and residential NOE exposure. However, NOE contact, especially surrounding greenness, was statistically significantly tied to better mental health. There were indications that these relationships were stronger for males, younger people, low-medium educated, and Doetinchem residents. Perceived stress was a mediator of most associations, and physical activity and social contacts were not. CONCLUSIONS: Our findings indicate that contact with NOE benefits mental health. Our results also suggest that having contact with NOE that can facilitate stress reduction could be particularly beneficial.