This cross-cultural study explores the relationship of natural outdoor environment (NOE) use with NOE access. Most urban planning recommendations suggest optimal accessibility to be 300 m–500 m straight distance to spaces with vegetation of at least 1 hectare. Exploring this recommendation, we used data (n = 3947) from four European cities collected in the framework of the PHENOTYPE study: Barcelona (Spain), Doetinchem (The Netherlands), Kaunas (Lithuania) and Stoke-on-Trent (United Kingdom) to obtain residential access to NOE (straight or network distances, using 300 m and 150 m buffers, to NOE larger than 1 hectare or 0.5 hectare) and use of NOE (i.e., self-reported time spent in NOE). Poisson regression models were used to examine the associations between residential access and use of NOE. The models with the strongest association with time spent in NOE in the combined sample were for those living within 300 m straight line distance to either 0.5 ha or 1 ha NOE. Noting that the only indicator that was consistent across all individual cities was living with 150 m network buffer of NOE (of at least 1 ha), this warrants further exploration in reducing recommendations of 300 m straight-line distance to 150 m network distance to 1 ha of NOE for a general indicator for cities within Europe.