Background Urban residents may experience cognitive fatigue and little opportunity for mental restoration due to a lack of access to nature. Natural outdoor environments (NOE) are thought to be beneficial for cognitive functioning, but underlying mechanisms are not clear. Objectives To investigate the long-term association between NOE and cognitive function, and its potential mediators. Methods This cross-sectional study was based on adult participants of the Positive Health Effects of the Natural Outdoor Environment in Typical Populations in Different Regions in Europe (PHENOTYPE) project. Data were collected in Barcelona, Spain; Doetinchem, the Netherlands; and Stoke-on-Trent, United Kingdom. We assessed residential distance to NOE, residential surrounding greenness, perceived amount of neighborhood NOE, and engagement with NOE. Cognitive function was assessed with the Color Trails Test (CTT). Mediation analysis was undertaken following Baron and Kenny. Results Each 100 m increase in residential distance to NOE was associated with a longer CTT completion time of 1.50% (95% CI 0.13, 2.89). No associations were found for other NOE indicators and cognitive function. Neighborhood social cohesion was (marginally) significantly associated with both residential distance to NOE and CTT completion time, but no evidence for mediation was found. Nor were there indications for mediation by physical activity, social interaction with neighbors, loneliness, mental health, air pollution worries, or noise annoyance. Conclusions Our findings provide some indication that proximity to nature may benefit cognitive function. We could not establish which mechanisms may explain this relationship.