Степашин согласился. Ему поручили заниматься Чечней. Но когда Александр Лебедь в 1996 году стал секретарем Совета безопасности и помощником президента, он отставил Степашина от чеченских дел, которыми занялся сам.

В газетном интервью Степашин говорил с уважением о незаменимом опыте работы в аппарате правительства. Есть такие нюансы, тонкости, о которых, даже будучи министром, не узнаешь. Это все еще пригодится, заметил Сергей Вадимович, и не ошибся... Его опыт показывает, что никогда не надо отчаиваться.

Летом 1997 года разразился скандал из-за министра юстиции Валентина Ковалева. Путин, который работал тогда в администрации президента, предложил кандидатуру Степашина, которого хорошо знал по Ленинграду. Он позвонил Степашину:

— Сергей, надо встретиться.

Разговор происходил в парке возле Белого дома. Путин прямо сказал:

— Ковалев ушел. Почему бы тебе не стать министром юстиции? У тебя опыт. К тому же ты доктор юридических наук.

Степашин ответил, что с удовольствием станет министром, а то надоело бумажки носить, но поинтересовался:

— А как отнесется президент?

— Не знаю, что получится, — уклончиво ответил Путин, — но я готов тебя поддержать.

Через два дня Степашина вызвал Черномырдин и официально предложил возглавить министерство юстиции.

Назначение не всем понравилось. Одна из газет писала так: «Генерал-лейтенант действующего резерва ФСБ Сергей Степашин — человек, по сути дела спровоцировавший бойню в Чечне, вместо скамьи подсудимых занял кресло министра юстиции».

Но очень быстро его деятельность стали оценивать положительно. До него министерство юстиции считалось второразрядным и незаметным. Степашин с его административным даром и нерастраченной энергией сразу же стал заметным. Он хотел показать, что справится с любой должностью. Министерство получило большие полномочия. В частности, он добился передачи тюрем и колоний из МВД в ведение министерства юстиции.

Весной 1998 года вслед за Черномырдиным в отставку отправили министра внутренних дел Анатолия Куликова. Это было неожиданностью для всех, прежде всего для самого министра, который стал генералом армии, вице-премьером и считал, что Ельцин у него в долгу хотя бы за операцию с Лебедем. Но в Кремле считали, что Куликов придерживается ястребиных взглядов, недостаточно гибок и не улавливает настроений президентской команды. А на такой должности нужен свой человек.

Кем его заменить? Вспомнили о Степашине.

Его вытащили прямо из-за праздничного стола и вызвали в Кремль. Глава президентской администрации Валентин Юмашев сказал, что Борис Николаевич предлагает Степашину возглавить министерство внутренних дел. Сергей Вадимович для порядка сказал, что он и в министерстве юстиции совсем недавно, и неудобно так быстро менять место работы.

Юмашев выслушал Степашина и обещал передать его слова президенту. Это была суббота, а в понедельник утром его вызвал президент. Борис Николаевич был крайне любезен и тут же подписал указ о назначении Степашина. Юмашев отвез его в министерство и представил членам коллегии.

Степашин оказался первым министром внутренних дел, которого почти не критиковали. Он вел себя активно и разумно. Расставил на ключевые должности профессионалов с большим опытом оперативной работы. Проводил масштабные операции по очистке отдельных территорий от преступных элементов и нещадно боролся с преступниками в собственном ведомстве. Возможно, это был лучший министр внутренних дел за последние годы.

И тут Ельцин еще раз к нему пригляделся и решил, что надо бы попробовать Степашина в роли премьера.

27 апреля 1999 года Сергей Вадимович был назначен первым заместителем главы правительства, оставаясь на посту министра внутренних дел. Стало ясно, что он и заменит Примакова. Это произошло через две недели, 12 мая, когда Степашину было поручено возглавить правительство.

В этот день Степашин выступал на Высших академических курсах МВД для руководящих сотрудников местных аппаратов. Он призывал своих подчиненных к смелости:

— За каждым из вас стоит и министр, который никогда никого не бросит и никого не предаст.

Сергей Степашин однажды произнес ключевую фразу: «Я пришел с этим президентом, я с ним и уйду». Но одной только искренней преданности президенту оказалось недостаточно, чтобы остаться на посту главы правительства.

Его назначение произошло при очень странных обстоятельствах. Ельцин до последнего момента колебался и не знал, кого предпочесть — Степашина или министра путей сообщения Николая Емельяновича Аксененко.

Сначала Ельцин вроде бы остановился на Аксененко и даже назвал его фамилию в телефонном разговоре с председателем Государственной думы Геннадием Селезневым. А потом все-таки прислал в Думу письмо с просьбой одобрить кандидатуру Степашина. Селезневу оставалось только развести руками: