W wyniku nieudanej akcji w Budionnowsku, Stiepaszyn wraz z szefami pozostałych rosyjskich resortów siłowych stracił stanowisko.
W listopadzie 1995 został mianowany kierownikiem departamentu administracyjnego Aparatu Rządu Federacji Rosyjskiej. 2 lipca 1997 został powołany na stanowisko ministra sprawiedliwości oraz wszedł w skład Rady Bezpieczeństwa. 28 kwietnia 1998 mianowany został ministrem spraw wewnętrznych, zaś od kwietnia 1999 był jednocześnie pierwszym wicepremierem. 12 maja 1999 prezydent Borys Jelcyn powierzył mu funkcję szefa rządu. Jednak już 9 sierpnia 1999 został zdymisjonowany, a jego miejsce zajął Władimir Putin. Przyczyny i okoliczności dymisji Stiepaszyna pozostają niejasne. Wiele wskazuje na to, że już wcześniej dla Stiepaszyna zaplanowano rolę „tymczasowego” premiera. Wśród nieoficjalnych powodów dymisji wymienia się brak zdecydowanych działań na rzecz zaplecza politycznego Jelcyna, jak i niezdecydowanie w działaniach przeciwko Czeczenom. Został wobec tego zastąpiony przez Putina, dla którego szykowano rolę następcy odchodzącego prezydenta JelcynaPeter Baker, Susan Glassner, Cień Kremla. Rosja Putina, Warszawa 2005 (), s. 61-64Boris Reitschuster, Władimir Putin. Dokąd prowadzi Rosję?, Warszawa 2005 (), s. 59–60..