[[1990]]-ben még az [[Ukrán Szovjet Szocialista Köztársaság|Ukrán SZSZK]] Legfelsőbb Tanácsába választották meg képviselőként a Dnyipropetrovszki terület egyik egyéni választókerületéből. [[1992]]-ben indult a független Ukrajna első szabad parlamenti választásán is, és ismét képviselőnek választották. 1992 márciusában Ukrajna elnöke kinevezte a Dnyipropetrovszki területen elnöki megbízottá, így 1992. június 6-án lemondott a parlamenti mandátumáról. Lazarenko, habár az elnökválasztáson [[Leonyid Kravcsuk]]ot támogatta, szoros kapcsolatokat épített ki a szintén dnyipropetrovszki [[Leonyid Danilovics Kucsma|Leonyid Kucsmával]], akit [[1994]]-ben elnökké választották. Kucsma még abban az évben kinevezte Lazarenkót a Dnyipropetrovszki Területi Állami Közigazgatási Hivatal vezetőjévé, és egyúttal a Területi Tanács elnökévé is választották. Leonyid Kucsma elnök [[1995]]. szeptember 5-én első miniszerelnökminiszterelnök-helyettessé nevezte ki, majd Jevhen Marcsuk menesztése után [[1996]]. május 28-án miniszterelnökké nevezte ki. (A [[Legfelsőbb Tanács (Ukrajna)|Legfelsőbb Tanács]] nem hagyta jóvá, mert az elnökkel kötött alkotmányos alku értelmében a parlament abban az időben ideiglenesen lemondott erről a jogáról.) Még miniszterelnöki idejének elején sikertelen bombamerényletet követtek el ellene a [[Boriszpili nemzetközi repülőtér]]ről [[Kijev]]be vezető autópályán, ahol feltartóztatták a kocsiját. Az ukrán média egy része [[Jevhen Scserban]]t gyanúsította a merénylet megszervezésével. (Később, Scserban meggyilkolásakor pedig Lazarenkót tartották a merénylet megrendelőjének.) Még miniszterelnök-helyettesként kezdte kiépíteni kapcsolatait [[Julija Volodimirivna Timosenko|Julija Timosenkóval]], aki abban az időben az orosz gáz importjával foglalkozó, monopolhelyzetet élvező állami vállalat, az Ukrajna Egységes Energia Rendszere ''(JEESZU – Jedina Enerheticsna Szisztema Ukrajini)'' elnöke volt. Az elsősorban a dnyipropetrovszki politikai és pénzügyi körök érdekeit képviselő miniszterelnökként egyre terebélyesedő konfliktus alakult ki közte és Ukrajna másik meghatározó érdekcsoportja, a [[doneck]]i pénzügyi-ipari körök (az ún. „Donecki-klán”) között. Minden idők egyik legkorruptabb ukrán politikusa, a Transparency International [[2004]]-ben az addigi nyolcadik legkorruptabb politikusnak nevezte.<ref>A Transparency International szervezet a [http://www.transparency.org/publications/gcr/download_gcr/download_gcr_2004 Global Corruption Report 2004] kiadványában 114–200 millió USD közé teszi a Lazarenko által elsikkasztott állami vagyont.</ref>
1997 közepére Lazarenko kiesett Kucsma elnök kegyeiből. Ennek legfőbb oka az volt, hogy Lazarenko miniszterelnökként Kucsma potenciális vetélytársává nőtte ki magát, és indulni akart az 1999-es elnökválasztáson. Az addig soha sem betegeskedő Lazarenko 1997 júniusában hirtelen kórházba vonult. Az elnökkel megromlott kapcsolata miatt 1997. július 2-án lemondott a miniszterelnöki posztról.
