Personal experience, the best diet I've encountered is this: ~500 calories a day.

That's it. Your goal is to be as full as possible on those 500 calories, however; prioritize protein. 3.1 ounces of very lean meat (96/4 beef, chicken, turkey, etc.), good spices, and some vegetables can get you in (and fill you up!) at ~250 a meal. Drink a glass of water before each meal if you're still unsatiated. (Multivitamins on this diet are -essential-, however.) Allow yourself to eat a little more as necessary.

Start walking. Jog intermittently; increase the amount of jogging as you lose weight. Don't push it, when you're heavier, it's -really- easy to hurt yourself, personal experience speaking here.

Your goal in this period is to lose around a kilogram of weight per week. You'll lose muscle, too, but not as much. After about a month, personally, I was so thrilled with the success of the weight loss I didn't -want- to go off the diet. Food was less tempting than the weight loss.

Once you're thinner, I recommend taking up jogging. (I personally wouldn't, until you're in better shape, just because of the high risk of shin splints, which make what is otherwise a pleasant exercise miserable.)