First off thank you for doing what you are doing!!!
So basically it seems as though your lungs are what are primarily out of shape, so that is what you need to work on first.
Start by jogging what you can...when you can. Simply start slow and focus on breathing. In through the nose out through the mouth. I know it seems impossible when you just want to take a big gasp of air. That is a bad idea though. So do that a few small times a day. Like jog for 3-5 minutes a couple times a day and focus solely on that for the first few days. Once you feel that you are comfortable and can breath like that better then focus on the running.
Most people can run a 1/4 of a mile without much haste. It is pretty easy to do that. Say it took you two weeks to get the breathing down. Now you have 6.5 months left.
We'll say that 190 days... to get to your goal.
Day one: Run a 1/4 mile as fast as you can. Give yourself 6 minutes to do it.
Day 2: Do it again
Day 3: Do it again
Day 4: Do it in 5 minutes
Day 5: Doit in 5 minutes
Day 6: Take a day to rest
Day 7: Run the 1/4 in 5 minutes and run another 1/4 so 1/2 total. Give yourself 12 minutes.
Day 8: Do it again
Day 9: Do it again
Day 10: Rest today
Day 11: Run the 1/2 mile in 10 minutes. Then run another 1/4 mile: Total time 18 minutes.
Day 12: Do it again.
Day 13: Do it again
Day 14: Rest today.
Day 15: Run 3/4 mile in 18 minutes then run another 1/4 mile Total time 22 minutes.
Day 16-19: repeat
Day 20: Run 1 mile in 18 minutes
Day 21: Rest today.
Day 22-25: 1 mile in 15 minutes
Day 26: Run 1 mile, then 1/4.
Just continue building up like this everyday and you will be there before you know it.

ik heb ook bij de de landmacht geweest na de opleiding had ik daar geen moeite mee ma heb altijd al aan sport gedaan heb altijd wedstrijden zwemmen gedaan da kan u ook helpen bij uw training zonder da ge het zelf beseft! al uw spieren zetten zich voledig in !! laat me nog ma weten hoe da ge vordert!! grtz mario

Skipping the exercise part except to say that for motivation and to get in better mental/physical condition I would suggest taking classes in Yoga, Karate/Judo/Aikido/Kung Fu, and a dance class such as Ballet (What? yeah looking at pretty girls while holding your legs or arms out till it hurts--and you try to keep up--plus get used to the drill sergeant routine!) or Modern/Hip Hop. These all build stamina and the group effect adds motivation.

Mainly I would say optimize your diet like other athletes do, thinking of a pyramid based firstly on foods that can be eaten raw or juiced--this is a basic nature/survival diet, secondly foods that take little cooking like steamed vegetables or lightly cooked meats. The basics for the above is that vitamins and enzymes are destroyed by cooking and overcooked (charred) food has toxic effects. If you can pay a little more organic food has more nutritional value besides better taste. Shun junk food, candy, and eating like a kid--now you need warrior monk discipline.

A good vitamin supplement helps, but even better is natural supplements with high nutrient value: bee pollen (loose granules), nutritional yeast, omega oil mix, and if needed natural nutraceutical or hormonal boosters such as weightlifters get at health food stores. Jarrows is a good inexpensive brand. Some natural herbs/supplements boost testosterone and immune systems, without taking synthetic steroids, etc. & it would help to take them in tinctures or tea.

Your story seems just like mine. So, the remedy too should be like that worked for me. Here are some tips which really helped me out to win my School Marathon Race. Before that, I too was very bad at long distance running (although I was very good at 100 Mts. & 200 Mts. sprints). Now, I am a football trainer and can easily run 5-6 miles, faster than my students. Here we go;

1. The basic and the most important thing about building up stamina and jogging/running long distances is "Rhythm" which all my friends seem to have missed here. You must and must breathe in a rhythm and you must jog rhythmically. You are out of breathe as soon as rhythm is broken. Our football coach had taught me this great secret and this works miracle. Try to maintain a rhythm between your inhalation, exhalation and try to step accordingly. For example, 2 steps - exhale and next 2 steps - inhale.

2. The second best tip is to use your centre of mass to pull you forward. This is called "Rolling". This is very scientific and reduces your efforts to a great extent. For this, you need to lean a bit forward (from your waist) while you are jogging or running. You might have seen athletes doing this in track and field events. Now, when you lean forward, most of your body wait hangs forward and your legs try to leap forward to maintain the balance and to keep you from falling on your face. Now, as you keep leaning forward, the legs keep leaping forward and this makes you run or jog, even if you do not want to do so. This saves a great effort which is otherwise needed to pull your legs. So, you don't actually jog. Rather, you "Roll" here. Avoid leaning back as far as possible. This drags your body backwards and you need to use tremendous energy to pull it forward.

3. Like my friends @ashtenmeadows & @omicron have said here, you need to start with a little jogging and more rest in between and then go on increasing the jogging time and decreasing the rest period. Here, like @omicron have said, the rest should never be a total immobilization. If you ever try to sit, then there are very much chances that your muscles will resist any further action. So, you must keep moving. Walk, or jog very slowly in the rest periods.

4. If you go to gym, concentrate on "Breathing" exercises. This is a sort of bench-press which is done with light weight dumb-bells. For details on how to do it, you should take guidance of your trainer. Still, for your information, this is done as follows. Lie on a narrow bench on your back. Hold two light dumb-bells in your two hands. Bring the two dumb-bells together above your chest, keeping your hands straight, without folding your elbows. Keep it just straight and above your collar-bone. Now slowly, keep breathing in and bring the two hands down on either sides, a bit below your shoulder level. Stop breathing in. Now, breathe out slowly and bring the hands back to their original position, slowly releasing the breathe. Repeat it 10-12 times in each set and do 3 sets in starting.

5. Try to breathe in through your nose and breathe out through your mouth. This is a great tip but a bit hard to beginners. When you are done with it, try to breathe out with your mouth closed. This further improves breathing and improves capacity of lungs and strengthens them. This is very scientific tip.

6. Use the best jogging shoes available. Heavier shoes or those with harder soles reduce efficiency to a great extent.

7. Whenever you have time, breathe in full-lungs and flung open your hands on both sides. Bring them together when you breathe out. This is like mimicking the bench-press breathing while standing, without dumb-bells. This also helps a lot.

8. Stretch as much as you can. Stretching relaxes muscles.

9. Try to keep something like a chewing gum in your mouth to avoid opening of mouth while jogging.

10. Don't jog with a heavy stomach (Don't eat or drink anything just before and after you jog. Keep an interval of at least 1 hour).

11. You haven't mentioned your body-weight. If you are on the heavier side, try to reduce it. This also improves performance.

12. Try not to practice alone. Accompany a good long distance jogger/runner whom you know. The sense of competition and going ahead of him (at least, keeping up with hm) will certainly improve performance. When you have no competitor, you don't feel that urge to prove yourself. Isn't it?

13. Football or hockey are two games that work miracle in building stamina and lung-capacity. They are highly recommended. But after you are fine with at least 1 mile.

14. Don't smoke. If you cannot follow this, at least reduce smoking. Smokers can never run.

15. Don't practice everyday. It is best to practice every alternate day. This relaxes muscles, gives them sufficient rest and help building them up. But first, continue it at least for 4 weeks with rest only on Sundays.

16. Now something psychological. Don't think that you are attempting 1 mile before you start running or while you are running. This discourages the runner. Rather, think that you will be attempting 4 laps of 400 meters each. This makes thing look lot easier.

17. For a schedule, refer to what @ashtenmeadows have advised. Mine is not very different from that and therefore I am not repeating it here. He has given a good schedule.

But whatever you do, don't forget "Rolling" , breathing through nose and that psychological tip.

Hope that helps.

Try the tips.

All the very best. Thanks

You have to do something you love while you do it. Focusing on something else, will make you hurt less. Ipod, basketball, racketball, etc. I recommend interval training that is programmed on any basic treadmill. IE sprinting, jogging, walking. Mix it up a little so your muscles don't get bored. Stretch and stretch and stretch. Start slow. Here is an interesting article. http://www.timeforfitness.com/running/keep_running.htm

This isn't quite a plan, but my husband is in the military and this is how he improved his run time.

Wherever you run, mark it off be about 1/8 of a mile in sections. One way to do this is to simply know what objects are about the distance you are running. For example - third telephone pole or a certain neighbors mailbox.

Anyhow, run your 1/8 of a mile, walk the next 1/8 mile. Keep repeating this until you have reached your goal.

I don't know if it works for everyone, but a lot of people in his unit have tried it and it's worked for them.

Good luck and thanks (in advance) for your service.

You've gotten some good answers so I'll just add a bit of info from the military perspective. Ask your recruiter what he has for a PT program that you could participate in. Others in delayed entry could be motivators for improving your ability to meet the PT goals. It also helps to have run in formation before you go. Plus there is something about running with a structured group which keeps you going for more steps than you will do on your own.

Good luck to you as you make this big step forward. Thank you for your willingness to volunteer to serve!

One possibility that will provide you with free coaching, mentoring, and a support group while you go from couch potato to marathoner is the Leukemia and Lymphoma Socitey (LLS) Team in Training (TNT) program. If you go to http://www.teamintraining.org/ you can see which chapter is closest to your house. Contact the chapter and they will let you know when the next informational meeting is (you're in luck as it is currently the start of a new season). Once the season starts they will take you from not being able to run even 1 mile to being able to complete a marathon (26.2 miles) within about 4 or 5 months. TNT have trained over 420,000 ordinary people to successfully complete half-marathons, marathons, century bike rides, triathlons, etc. over their 21 year history.

In addition to all the above benefits, you will be raising funds to help fight blood cancers, and will have an "honored team-mate" who is either currently suffering blood cancer, or is a survivor, which is highly motivational. Personally, I'm not a runner, so I signed up for the bicycling program, and within 3 months TNT trained me from being able to ride a leisurely hour on my bike to completing a 100 mile bike ride in just over 6 hours, including finishing the first leg of 23 miles in an hour. You can read more about that experience at http://www.associatedcontent.com/article/2220001/getting_fit_while_raising_funds_to.html .

The bottom line is that if you go with TNT they will provide all the training, teaching, motivational aspects, etc. You just need to raise the minimum amount of funds required for the marathon you sign up for, and run according to their training schedule (part of the training runs will be with your team-mates, while others will be on your own or with whoever you arrange to run with you). They will even cover your expenses to travel to the marathon, lodging, dinner the night before, a celebration dinner after the event, and even a jersey.

maybe start on a treadmill or stationary bike...

or do something you like... like skiing to increase your cardio vascular fitness.

In general, if you're getting out of breath quickly, it means you're running/jogging too fast. Your legs may be in good enough shape to handle a long run, but your heart and lungs need to be eased in to it. Any cardiovascular exercise will help with that, but since you have a running goal to meet anyway, you might as well focus your training on that.

If you want a good, well-planned regimen to get you started, you should check out Runner's World's 8-Week Beginning Runner's Training Program:
http://www.runnersworld.com/article/0,7120,s6-380-381-386-9397-0,00.html

It's basically 4 days of interval training (you walk x minutes and run y minutes, then repeat that a set amount of times), 2 days of walking, and one day off each week. The first week, you're doing 10 repetitions of running for 1 minute and walking for 2 minutes (for a total of 30 minutes). Each week they change the length of the walking/running intervals around (and they'll change it around from day to day inside those weeks, too), making your running intervals longer, until at the end you're running the full 30 minutes. The goal is to get you running (or at least jogging) consistently for 2 miles by the end of the 8 weeks. The interval training aspect lets you keep your heart rate up without making you gasp like a fish out of water. In general, you should aim to have your heart rate get between 60 to 80% of your estimated highest heart rate. You can get a ballpark number for your age here:
http://www.mayoclinic.com/health/target-heart-rate/SM00083
There's a more detailed discussion here (or just google "target heart rate" and look around):
http://www.thewalkingsite.com/thr.html

Something you can do in lieu of taking your pulse during a workout is doing the "talk test". It's basically what it sounds like--if you can't talk relatively comfortably while running, you're probably overtaxing your cardiovascular system, which means you're running too fast.
http://www.webmd.com/fitness-exercise/guide/20061101/talk-test-measures-exercise-intensity

In addition to giving you a good workout schedule, the Runner's World article I linked to will give you tips on what to eat/drink prior to your workout, when to do your stretches, how you should warm up and cool down, etc. It's a good article all around, and the site should be able to help you with most issues that may come up during your training. You may want to take a look at their nutrition/diet information, too (depending on how strenuous your whole workout routine ends up being, and what/when you eat now, you may want to switch up your eating habits a bit to maximize your benefits). Another thing that may or may not be on the Runner's World site is a description of proper breathing. Learning how to breathe right while exercising can be a big help. Read this:
http://askcoachjenny.runnersworld.com/2008/02/happy-trails-co.html

That first 2 miles is supposed to be the hardest thing to get used to. After you're fit enough to do that, it's only a question of slowly adding more time to your routine, and working on your speed. You may want to think about adding a little weight into the mix toward the end of your 7 months (I'm guessing running while carrying a load is probably in your future--you may as well get a bit of practice in early). When you're adding to your workout (be it in duration or intensity) try not to go overboard with it. Generally speaking, the rule of thumb is to add no more than 10% (duration or intensity) per week. So, at the end of the 8 week program, add 3 minutes duration per workout during your next week, then maybe a little over 3 more minutes the week after that, and so forth. This is to help keep you from injuring yourself. Not all sports medicine people believe this rule is helpful for beginning runners. If I were you, I would try to stick to the 10% rule as far as duration goes, but work on interval training during your runs (basically, do something similar to the 8-week program, only with the "walking" portion of the interval days being "running/jogging at your new comfortable pace" and the "running" portion being "running noticeably faster than usual". It's a good way to start running faster, which is something you should work on once you get your cardiovascular system fit enough to do the 2 mile run without stopping.

You probably have pretty strong legs right now, but you may want to do some lower body exercises two or three times a week, in addition to running. This will do 2 things--it will help you get faster as a runner, and it will also help prevent you from getting injured. Here's a 10 week plan for strength training for runners (it looks like it was originally posted to help a gym group prepare for a long race of some sort--it would probably be okay for your purposes):
http://www.berry.edu/academics/education/elementary/documents/StrengthTrainingforRunners.pdf

You can read a bit more about strength training for runners here:
http://www.active.com/page18720.aspx

A few last points: Vary your workout as you go along. Running at the track will be good for you (and convenient), but if you can find a place to run with hills (especially once you've conquered the 2 mile run), that will help you work some muscles a flat track just won't be getting. It'll probably be a closer approximation of what you'll be doing in basic, too. You can always run on one of those incline treadmills, too. If you can find a friend to run with you, it will help you stick to your routine (plus, you'll feel much less silly doing the talk test). If you feel like you're putting too much strain on your body, you probably are--dial it back a bit. It's better to slow your progress a little than to really hurt something and stop it all together.

I hope this helps. Good luck!

You've got to build up your endurance. You do this by running longer distances for longer times each time you set out to run. Each time, give yourself a goal to surpass your previous effort. Don't try to do it all in a week. It takes time to build up your endurance, but don't push yourself beyond your capacity. Listen to your body, it's the best barometer to let you know how far you can go.

First thing I would like to say is if you were that winded after running maybe you should start out at a shorter distance and work your way up. My cousin was in the Marines and retired a few years back. He has a video out that help you get into shape. Here is the address:www. Motova8.com. Right now he only has 1 video out and working on another. Iam pretty sure this might be of some help to you.

Good Luck !!

He is the one standing on the right.

http://www.flickr.com/photos/timzeug/512232831/