Lebed lubas ohjeldada nii tänavakuritegevust kui ka valitsuse korruptsiooni , samuti lubas lõpetada ebapopulaarse Esimese Tšetšeenia sõja. Majanduspoliitika osas andis ta mõista, et toetab käimasolevaid turumajanduslikke reforme, kuid jäi teadlikult ebamääraseks.
Tema populistliku retoorika tõttu võrreldi Lebedit Vladimir Žirinovskiga. Lebedi stiili ja isiklikku karismat peeti tema kampaania jaoks olulisemaks kui tema poliitilist sõnumit ennast. Kuni maini flirtis Lebed võimalusega moodustada teiste kandidaatidega kolmandate jõudude koalitsioon, kuid need läbirääkimised ebaõnnestusid.
Valimiste esimeses voorus 16. juunil 1996 saavutas ta Jeltsini ja Zjuganovi järel kolmanda koha, kogudes 14,7% häältest. Vastutasuks Lebedi toetuse eest vallandas Jeltsin Lebedi rivaali kaitseminister Pavel Gratšovi asendades ta Lebedi palvel Igor Rodionoviga. Pärast valimiste esimest vooru nimetas Jeltsin kindral Lebedi Venemaa Julgeolekunõukogu sekretäriks.
Mälestuse jäädvustamine
Mälestusmärk Aleksandr Lebedelile Benderis
8. veebruaril 2003 anti Krasnojarski krai seadusandliku kogu otsusega ühele Lääne-Sajaanide nimetule mäetipule nimeks Aleksandr Lebedi mäetipp
juulis 2007 anti Transnistrias välja Lebedelile pühendatud margiseeria
12. juunil 2012 avati Transnistrias Benderi linnas mälestusmärk Aleksandr Lebedelile