Alexander Lebed blev født i 1950 i den kosakiske by Novocherkassk i Rostov-oblasten. I sin ungdom var han ikke en dårlig elev, men foretrak boksning og skak. Han voksede op i fattigdom. Hans far var en tømrer, der blev idømt syv år i en Gulag arbejdslejr for at ankomme for sent til arbejde to gange, og var vidne til
Novocherkassk massakren i 1962. I den tid arbejdede han på en fabrik. Han var fast besluttet på at blive faldskærmssoldat og sluttede sig til Ryazan Guards Higher Airborne Command School i 1969, hvor han blev en kadet platoon og kompagnichef, mens han var der. I 1982, som officer i de sovjetiske luftbårne tropper, blev Lebed bataljonchef i Afghanistan under den sovjetiske krig der. Under sin tid i Afghanistan, blev Lebed populær hos tropperne under hans kommando. Han beklædte denne stilling indtil 1982, hvor han deltog i Frunze Military Academy. Blandt hans pligter var at være medlem af begravelsesafdelingen i perioden med mange dødsfald blandt det sovjetiske gerontokrati, herunder tre sovjetiske herskere.