The increasing consumption of high-fat western foods combined with a lack of exercise is a major contributor to the burden of obesity in humans. Aerobic exercise such as running is known to provide metabolic benefits, but how the over-consumption of a high fat diet (HFD) and exercise interact is not well characterized at the molecular level. Here, we examined the plasma proteome in mice for the effects of aerobic exercise as both a treatment and as a preventative regime for animals on either HFD or a healthy control diet. This analysis detected large changes in the plasma proteome induced by the HFD intervention, such as increased abundance of SERPINA7, ALDOB, APOE, and down-regulation of SERPINA1E, CFD (adipsin), LIFR. Some of these changes were only significantly reverted using aerobic exercise as a preventative measure, but not as a treatment regime. To determine if either the intensity, or duration, of exercise influenced the outcome, we compared high-intensity interval training (HIIT) and endurance running. Endurance running slightly outperformed HIIT exercise, but overall both provided similar reversion in abundance of plasma proteins modulated by the high-fat diet including SERPINA7, APOE, SERPINA1E, and CFD. Finally, we compared the changes induced by over-consumption of HFD to previous data from mice fed an isocaloric high saturated fat (SFA) or polyunsaturated fat (PUFA) diet. This identified several common changes including increased APOC2 and APOE, but also highlighted changes specific for either over-consumption of HFD (ALDOB, SERPINA7, CFD), SFA-based diets (SERPINA1E), or PUFA-based diets (Haptoglobin - Hp). Together, these data highlight the importance of early intervention with exercise to revert HFD-induced phenotypes and suggest some of the molecular mechanisms leading to the changes in the plasma proteome generated by high fat diet consumption in both mice and humans.