Background: Despite the large number of studies on beneficial effects of the natural outdoor environment (NOE) on health, the underlying mechanisms are not fully understood. Objective: This study explored the relations between amount, quality, use and experience of the NOE; and physical activity, social contacts and mental well-being. Methods: In this cross-sectional study, data on GIS-derived measures of residential surrounding greenness (NDVI), NOE within 300 m, and audit data on quality of the streetscape were combined with questionnaire data from 3947 adults in four European cities. These included time spent in NOE (use); and perceived greenness, and satisfaction with and importance given to the NOE (experience). Physical activity, social contacts and mental health were selected as key outcome indicators. Descriptive and multilevel analyses were conducted both on pooled data and for individual cities. Results: More minutes spent in the NOE were associated with more minutes of physical activity, a higher frequency of social contacts with neighbors, and better mental well-being. Perceived greenness, satisfaction with and importance of the NOE, were other strong predictors of the outcomes, while GIS measures of NOE and streetscape quality were not. We found clear differences between the four cities. Conclusions: Use and experience of the natural outdoor environment are important predictors for beneficial effects of the natural outdoor environment and health. Future research should focus more on these aspects to further increase our understanding of these mechanisms, and needs to take the local context into account.