African Americans with obesity have high rates of hypertension. Exercise has been shown to significantly reduce high blood pressure; however, effects through associated reductions in anxiety and depression are unclear. African American adults with either class 2 or 3 obesity (n = 86; Mage = 43.4 years) and either elevated blood pressure (n = 16) or stage 1 (n = 33) or stage 2 (n = 37) hypertension participated in a theoretically driven community-based weight-management program. There were significant increases in exercise outputs; while systolic and diastolic blood pressure, anxiety, and depression significantly decreased from baseline–month 6. Increased exercise significantly predicted reduced anxiety, depression, and diastolic blood pressure. Change in anxiety significantly mediated the relationship between exercise and both systolic and diastolic blood pressure changes. Increasing exercise from the equivalent of 1.5 to 4.5 moderate bouts/week reduced elevated blood pressure/hypertension in African American adults with severe obesity largely through their exercise-associated improvement in anxiety.