Rođen je u selu Radojinji, nedaleko od Nove Varoši, Srbija, 15. februara 1912. godine. Završio je samo tri razreda gimnazije u Novoj Varoši, jer je zbog neimaštine napustio školovanje i otišao u Beograd na izučavanje pekarskog zanata.

Nemirni duh Voje Lekovića nije se mogao pomiriti s uvjetima šegrtovanja, pa je morao da potraži nešto drugo. Radio je kao trgovački pomoćnik, konobar, akviziter i fizički radnik. Najzad se zaposlio kao privatni namještenik, i duže se zadržao na tom poslu, gdje se uključio u revolucionarni sindikalni pokret i ubrzo postao sekretar Sekcije trgovačkih pomoćnika.

Kada je zabranjen Savez sindikata privatnih namještenika, on se, kao član Partije, aktivirao u Savezu bankarskih, osiguravajućih, trgovačkih i industrijskih činovnika (SBOTIČ), ubrzo postavši član uprave ovog sindikata.

Jedan je od osnivača kulturno-umjetničkog društva "Polet" koje je, pod utjecajem komunista, postalo mjesto okupljanja revolucionarne omladine, bez obzira na profesiju. Zbog toga se "Polet" veoma brzo omasovio i postao trn u oku Specijalne policije, koja ga je zabranila.

Član je SKOJ-a od 1936. godine, a 1939. postao je član KPJ u kojoj je ubrzo, zahvaljujući svojoj aktivnosti, izabran za prvog sekretara obnovljenog SKOJ-a za grad Beograd. U martu 1940. godine izabran je za člana Pokrajinskog komiteta SKOJ-a za Srbiju. Na toj funkciji ostao je sve do okupacije Jugoslavije.

Aktivnost Voje Lekovića nije mogla ostati nezapažena od režima vladajuće buržoazije. Stavili su ga na policijski spisak, kao i ostale radničke borce, izložili progonima i maltretiranju. Godine 1940. uhapsili su ga i prognali u rodni kraj. Međutim, on je uspeo da se izvuče ispod kontrole policije i nastavi revolucionarni rad, kao ilegalac u Beogradu.

Odlukom Partije, u prvim danima okupacije on je preveden s omladinskog na partijski rad, i postao član Gradskog komiteta KPJ za Beograd i sekretar rejonskog komiteta za Karaburmu. U okviru Gradskog komiteta dobio je zadatak da koordinira sve akcije koje se budu vodile protiv okupatora i njegovih pomagača. Na tim zadacima ostao je do 6. septembra 1941. godine, kada je, odlukom CK KPJ i Glavnog štaba, koji je kasnije dobio naziv Vrhovni štab, poslat kao delegat Glavnog štaba u Sandžak za organiziranje ustanka.

Dolaskom u Sandžak, postao je komesar Glavnog štaba partizanskih odreda i Član Oblasnog komiteta KPJ za Sandžak. Kada je formirana 3. proleterska brigada (sandžačka), 15. juna 1942. godine, postavljen je za partijskog rukovodioca brigade u zvanju zamjenika komesara brigade. Na toj dužnosti je ostao kratko, da bi se ubrzo našao u dubokoj pozadini neprijatelja, na okupiranoj teritoriji, gdje je djelovao kao rukovodilac čuvene Zlatarske gerile, a kasnije, kao sekretar Oblasnog komiteta za Sandžak, sve do kraja rata. Bio je vijećnik AVNOJ-a i član njegovog Predsjedništva.

Poslije oslobođenja, zajedno sa svojim sa-borcima iz rata i revolucije, Voja Leković preuzima nove odgovorne dužnosti Partije, najprije u obnovi zemlje, a zatim u izgradnji socijalizma u Jugoslaviji. Na Petom kongresu, Voja Leković je izabran za člana CK KPJ, a na Prvom kongresu KP Srbije za člana Politbiroa CK.

Na prvim poslijeratnim izborima biran je za narodnog poslanika Savezne skupštine i Skupštine Narodne Republike Srbije. Prilikom formiranja prve Vlade Narodne Republike Srbije, povjeren mu je resor ministra industrije, a bi kasnije postao potpredsjednik Vlade, a zatim potpredsjednik Izvršnog veća vlade Srbije, potom i potpredsjednik Skupštine Srbije. Prelaskom na rad u Saveznu Skupštinu 1961. godine, izabran je za predsjednika Odbora za saobraćaj, a u sljedećem sazivu za predsjednika Komisije za društveni nadzor. Bio je član Savjeta Federacije.

Kao dosljedni revolucionar, Voja Leković je našao snage i vremena da bude jedan od inicijatora za stvaranje Pokreta gorana (kao predsjednik) koji je, osim učenja djece i omladine na tradicijama naše Revolucije, učinio neprocjenjivo veliku korist u zastrti i oplemenjivanju ljudske okoline.

Narodnim herojem proglašen je 27. novembra 1953. godine.