Background: Physical inactivity is a risk factor for poor mental health. The present study evaluates the association between mental health and physical activity levels according to the Healthy People 2010 guidelines in a large national sample. Methods: Participants (N = 41,914) were selected from the 2001 Behavioral Risk Factor Surveillance System. Primary predictor variable was physical activity level, and primary outcome measure was frequency of mental distress. Specific outcomes of anxiety and depressive symptoms were also measured. Results: Compared with those meeting the Healthy People 2010 guidelines, sedentary participants were 1.31 times more likely to experience 14 or more days of mental distress during the past 30 days (OR 1.31, 95% CI 1.16, 1.48), 1.34 times more likely to experience anxiety symptoms (OR 1.34, 95% CI 1.21, 1.49), and 1.22 times more likely to experience depressive symptoms (OR 1.22, 95% CI 1.10, 1.36). Comparing those participants falling short of the Healthy People 2010 recommendation with those meeting the guideline, no significant group differences were demonstrated relative to frequency of mental distress. Those meeting the recommendation were more likely to have 14 or more days of anxiety symptoms during the past 30 days (OR 1.10, 95% CI 1.02, 1.17). Conclusions: Our results suggest that being sedentary is clearly associated with more aversive psychological symptoms. However, performing enough physical activity to meet the Healthy People 2010 guideline may not be associated with better psychological status than minimal amounts of physical activity.