I used to be fat. Hell, I walked 6 km everyday (3km one way and back), and I'm on my feet all day at work. So exercise wasn't really an issue, it was my diet.
I stopped drinking pop. I used to live off Pepsi. I'd hardly ever drink anything else. So I went to water, water, water, apple/orange juice and milk. I cut back on sugary/fatty snack food. I used to eat a lot when I was bored (and not even hungry) and it's so easy to grab a snack, right? So I just stopped buying that shit when I went grocery shopping.
Also meat: Start eating a lot of chicken and fish. And eat your veggies.