I only run when I'm being chased, which doesn't happen that often... I'd say start with short distances and increase slowly and progressively combining 'long' distance at 60-70% max HR with short 10-15 minute sprint intervals. Also first learn to run. This may seem an odd remark, but most people cannot run. Train on the right technique (lots of sources on the inets). Form over quantity always! Also do 'normal' workouts with weights and flexibility workouts. One cannot run and get better by only running in my experience (which is mostly second-hand experience ).
Couch to 5K is an excellent programme - it keeps you progressing whilst still feeling as if you're achieving something.
I used something similar when I started running. Without it I know I would have tried to run, got horribly out of breath, decided i couldn't run, gone home and probably not tried again.