Background: The Metabolic Syndrome is the clustering of several cardiovascular risk factors for coronary heart disease and Type 2 Diabetes Mellitus. This syndrome is of public health importance due to its high prevalence and high correlation to all-cause, CHD, and CVD mortality. The purpose of the current study was to determine if a change in aerobic fitness in the treatment group significantly decreased the odds of Metabolic Syndrome at 6 and 18 months. Methods: There were 810 adult participants in this trial with above-optimal blood pressure and up to stage I hypertension. Participants were part of an advice-only control group or a treatment group where physical activity increases were the main component. Results: A change in aerobic fitness, independent of treatment status, was significantly associated with a decrease in prevalent Metabolic Syndrome at both 6 and 18 months (OR: 0.96, CI: 0.94 - 0.98 & OR: 0.96; CI: 0.94 - 0.98, respectively).