Regular exercise is associated with better mental health. This association is widely assumed to reflect causal effects of exercise. In this paper we propose that two additional mechanisms contribute to the association between exercise and mental health in the population-at-large: genetic pleiotropy and gene-by-exercise interaction. Both mechanisms assume heritability of exercise behavior and a partial overlap between the genes influencing exercise behavior and mental health. We review a number of large-scale studies in monozygotic and dizygotic twins that support these assumptions. Based on the importance of genetic factors in exercise behavior we develop a model for gene-by-exercise interaction that explains differences in voluntary exercise behavior by differential genetic sensitivity to the mental health benefits of exercise. We focus on the genetic modulation of acute mood effects of exercise and longer-term effects on self-esteem through genetic effects on exercise ability. If correct, our model calls for a change from 'population-based' to 'personalized' intervention strategies. © 2008 Elsevier Ltd. All rights reserved.