This research explores the hypothesis that gradients in environmental parameters influence the relationship between the nature experience and latent measures of psychological and physical health. The experiences of natural environments elicit numerous health benefits. These include health outcomes associated with physical activity as well as salutogenic psychological health benefits correlated with contact with natural environments and the removal of oneself from stress-inducing and fatigue-associated built and urban environments. As specific health attributes of natural environment visitation are further elucidated, it is time to consider the health costs linked with constraints in natural environment visitation. The present study aims to fill the knowledge gap regarding influences of environmental gradients on the nature experience and health outcomes relationship, with a primary focus on climate change. This is an opportune time to address this gap due to climate change vulnerabilities and the WHO’s study revealing neuropsychiatric diseases the number one burden of disease. The objectives of the study were to survey visitors at coastal parks where there are current, measurable environmental gradients and elucidate the relationship between perceived restorativeness of coastal environments and gradients in environmental quality. Adult visitors (n = 1,153) to three California State Parks and Beaches were surveyed on 75 randomly selected dates across all months of 2008. Participants completed a questionnaire on park visitation; perceived weather, environmental quality, and crowding; stress and perceived restorativeness; and demographic characteristics. Visitors perceived a greater environmental restorativeness when (1) temperatures were at or below monthly maximum temperatures; (2) mean sea level was below average; and (3) air quality/ozone concentrations were government-rated ‘Good’ (compared to ‘Moderate’ or worse). Visitors’ environmental quality perceptions were positively correlated with perceived restorativeness. The healthier the self-perceived air and water quality in park, the greater the environment was rated on the Perceived Restorativeness Scale. Finally, visitors on days with ambient temperatures above average were significantly more likely to state they would ‘Visit for a shorter time’ or ‘Definitely not visit’ when presented with hypothetical warmer temperature scenarios. Given results, projected global climate change could constrain the psychological health benefits associated with coastal park visitation. One of the most salient findings of this research is that the foremost environmental parameter contributions to perceived restorativeness in natural parks were perception of water and air quality, temperature difference from monthly mean, and sea level. Each of these parameters is projected to be adversely affected by global climate change. These impacts are likely to increase as climate change progresses and population density increases. Warmer ambient temperatures, with less space due to sea level rise, and less healthy environmental quality will surely offer a different experience within coastal parks. The significant contribution of both perceived and actual gradients in environmental parameters to the perceived restorativeness of coastal park environments has broad implications. Overall, the results advance the understanding of how environmental quality contributes to human – environment experience and explicates the need for further research to ascertain thresholds within parametric environmental gradients beyond which public participation in psychologically restorative activities is significantly impaired.