Current studies are showing that interval-type training/exercise is more effective for a weight loss program than steady pace cardiovascular workouts.
This, combined with an effective change in eating habits, seems like the way to lose fat and increase fitness.
http://www.cptips.com/intervl.htm