Positive environmental determinants of exercise frequency remain poorly understood. Knowing that people often value exercise for psychological restoration, we investigated the restorative quality of indoor and outdoor exercise settings as predictors of exercise frequency. We surveyed 319 members of fitness centers in Zurich that offer indoor and outdoor exercise alternatives. Outdoor settings were rated as more restorative. For each type of environment, restorative quality predicted the frequency of exercise in the past 30 days, independent of socio-demographic characteristics, expectations of exercise benefits, and personal barriers. We discuss the results with regard to the provision of exercise settings for urban populations.