Exposure to natural environments or to their audiovisual representations has a restorative effect on attention and short-term memory. However, higher-level cognitive processes, such as decision making, have been overlooked. Additionally, studies have generally compared natural environments perceived to be restorative, such as woods, with built environments perceived to be nonrestorative, such as roads with traffic, paying less attention to built environments that could be restorative, such as libraries. We examined whether exposure to potentially restorative natural or built environments (vs. nonrestorative built environments) would improve the ability to apply decision rules to multi-attribute choices, an important aspect of decision-making competence. Fatigued participants completed parallel versions of the Applying Decision Rules task before and after being exposed to audiovisual representations of these environments. Performance improved after exposure to restorative natural environments, remained unchanged after exposure to restorative built environments, and deteriorated after exposure to nonrestorative built environments. Restorative effects were partially mediated by self-reported fatigue, but not mediated by changes in attention control, emotional state, or motivation. We discuss the theoretical and practical implications of our findings.