Psychosocial factors, such as chronic mental stress and mood, are recognized as an important predictor of longevity and wellbeing. In particular, depression is independently associated with cardiovascular disease and all-cause mortality, and is often comorbid with chronic diseases that can worsen their associated health outcomes. Regular exercise is thought to be associated with stress reduction and better mood, which may partly mediate associations between depression, stress, and health outcomes. The underlying mechanisms for the positive effects of exercise on wellbeing remain poorly understood. In this overview we examine epidemiological evidence for an association between physical activity and mental health. We then describe the exercise withdrawal paradigm as an experimental protocol to study mechanisms linking exercise, mood, and stress. In particular we will discuss the potential role of the inflammatory response as a central mechanism.