Сразу после провала путча у КГБ СССР появился новый глава — назначенный Горбачевым внешний для чекистов человек, бывший министр внутренних дел Вадим Бакатин. Он, по сути, пришел уничтожать КГБ. В своей программе Бакатин предлагал раздробить организацию на несколько конкурирующих служб, предоставить самостоятельность республиканским ведомствам и главное — отказаться от идеологии чекизма. «„Чекизм“ — это постоянный поиск „врага“ по придуманной удобной формуле: „Кто не с нами, тот против нас“. „Чекизм“ — это постоянный ничем не ограниченный сыск и насилие над каждым, кто не укладывается в жесткую схему идеологии партии большевиков. Это полное слияние идеологии спецслужбы не с законом, а с идеологией правящей партии», — объяснял он.

В первую неделю пребывания на новом посту Бакатин впустил на Лубянку диссидента Владимира Буковского и дал ему телеинтервью, сидя в бывшем кабинете Андропова. Дальше — больше: вскоре само название КГБ перестало существовать. Бакатин переименовал ведомство в Межреспубликанскую службу безопасности и подарил своей команде черные футболки, на которых красной краской были зачеркнуты прежние аббревиатуры: ЧК, ГПУ, НКВД, МГБ, КГБ. За две недели до Дня чекиста Бакатин передал американским дипломатам схему расположения подслушивающих устройств в недостроенном новом здании американского посольства в Москве. 20 декабря он не поздравил сотрудников с праздником. Чекисты на Лубянке пришли в бешенство.

В ленинградском — теперь петербургском — управлении госбезопасности тоже появилось новое руководство. На смену Анатолию Куркову назначили Сергея Степашина — депутата и офицера МВД, поддержавшего Ельцина во время путча. Представлять Степашина приехал мэр города Анатолий Собчак — он назвал чекистов «цепными псами старого режима» и потребовал, чтобы они теперь так же рьяно работали на новую власть. На первой коллегии Степашин тоже произнес перед своими подчиненными речь. Смысл ее радикально отличался от программы Бакатина: «Я пришел не уничтожать вас, нам нужна сильная служба. Давайте смотреть, что творится в стране — развал полный, сейчас все всё потащат в разные стороны, начнется воровство. Попробуем это остановить».

Многие сотрудники Ленинградского КГБ в начале 1990-х уволились и ушли работать в бизнес — банкам и фирмам, торговавшим с Западом, требовались руководители в службы безопасности, кадров и внешнеторговых связей. Патрушев остался. Степашин, чтобы разобраться в обстановке, начал работать по выходным и в первую же субботу, обходя кабинеты, встретил Патрушева, тот тоже был занят делом. Они быстро сработались. Степашин назначил Патрушева начальником департамента экономической безопасности. В отличие от Бакатина, Степашин не забыл о Дне чекиста. 20 декабря он собрал подчиненных: «Чего мнетесь? Давайте отмечать, как положено».

Степашин возглавил петербургские органы безопасности в период коллапса советской, а потом и российской экономики. «У нас зарплата нивелировалась каждый день на 100–200 процентов, мы вынуждены были в совхозах закупать продовольствие», — вспоминал он. На новом месте ему пришлось заниматься новой для себя проблемой — в городе не хватало еды, и КГБ пытался контролировать возможные спекуляции и предотвращать хищения. В начале 1992 года депутат Ленсовета Марина Салье подготовила доклад о нарушениях в мэрии города и попросила Степашина их расследовать. Согласно докладу, подчиненный Собчака Владимир Путин и его заместитель Алексей Аникин «проявили полную некомпетентность, граничащую с недобросовестностью, при составлении договоров», по которым распределялись квоты на торговлю нефтью и другим сырьем. Если коротко, тогда в городе действовала схема: государство давало компаниям возможность обменять ценные ресурсы на продукты питания на Западе. Путин организовал процесс так, что лицензии получали знакомые ему фирмы, в контрактах стояли заниженные цены, а за неисполнение договоров нарушителей никак не наказывали. Степашин попросил проверить эту информацию Николая Патрушева — тот изучил все материалы и сказал, что никакой коррупции нет, обычная неразбериха. Встать на сторону депутата-демократа для него означало бы нарушить корпоративную солидарность.

Тем временем бакатинская реформа завершилась, не начавшись. После подписания Беловежских соглашений, формально ликвидировавших СССР, союзный КГБ перестал существовать и Бакатин остался без ведомства. Ельцин был заинтересован не в том, чтобы победить «чекизм», а в том, чтобы сделать спецслужбу подконтрольной — новая российская власть отчаянно нуждалась в инструментах управления страной. В следующие несколько лет КГБ пережил трансформацию, в которой была задействована почти треть букв русского алфавита — КГБ РСФСР превратился в АФБ РСФСР, затем в МБ РФ, потом в ФСК, и наконец, в 1995 году, — в ФСБ. У всех этих структур менялись и начальники: Ельцин искал наиболее лояльного и удобного для себя человека. В 1994 году руководителем ФСК стал Степашин, продемонстрировавший свою верность президенту во время восстания в октябре 1993 года. Конфликт между президентом и депутатами Верховного Совета вылился тогда в уличные столкновения, расстрел демонстрантов у телецентра «Останкино» и штурм парламента с применением танков. Степашин, и сам влиятельный депутат Верховного Совета, занял сторону Ельцина и был за это вознагражден. Став главой спецслужбы, он забрал к себе в Москву и Патрушева.

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

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

Через четыре дня Ельцин ввел режим чрезвычайного положения на территории Чечни. Под новый 1995 год на штурм чеченской столицы пошли уже полноценные российские войска. Эта операция тоже окончилась катастрофой. Бои за Грозный тянулись до февраля, в них погибли минимум полторы тысячи российских военных и 27 тысяч мирных жителей, город превратили в руины, чеченские сепаратисты отступили, но не были разгромлены. Когда Степашина спросили, какие выводы он сделал из этих провалов, он ответил: «Наша спецслужба должна быть сильной. Наделенной не только аналитическими и информационными функциями, не только возможностью что-то прогнозировать и предлагать, но и действовать. Спецслужбе нужны руки. Сегодня их у нас не оказалось».

На фоне катастрофы новогоднего штурма неудачу с ноябрьской операцией Степашина быстро забыли. В июне 1995-го произошло то, за что он не мог не разделить ответственность. Колонна чеченских боевиков под руководством Шамиля Басаева зашла в Ставропольский край и захватила больницу в городе Буденновск. В заложниках оказались более тысячи человек. Боевики требовали остановить войну и дать Чечне независимость.

Ельцин в этот момент был на саммите Большой семерки в Галифаксе, и основные решения принимал премьер Виктор Черномырдин. Он вел переговоры с помощью правозащитников, не согласовывая свои решения с силовиками, которые в этот момент готовили штурм больницы. В итоге группа спецназа начала штурм, но не смогла пройти дальше первого этажа. После этого переговоры возобновились. Договорились о том, что боевики отпускают заложников и возвращаются в Чечню. В качестве гарантии безопасности с ними поехали добровольные заложники. Степашин пытался убедить Черномырдина: «Есть задумка все-таки попытаться лупануть по автобусам. Возможны потери среди заложников. Но тогда замочим всех бандитов. Летчики готовы поднять вертолеты». В результате никто не принял решение «мочить» террористов, и они благополучно вернулись в Чечню. Черномырдин потом считал, что он свою задачу выполнил («Это был первый случай, когда жизнь простых людей была поставлена выше мифической „государственной целесообразности“»), а силовики свою — провалили. Степашин подал в отставку.

Патрушев не принимал непосредственного участия в разработке операции в Буденновске, но должен был сделать для себя вывод: политики, ведущие мирные переговоры с боевиками, всегда сделают силовиков крайними. После отставки Степашина он продолжил служить в ФСБ, но его карьерный рост остановился. В 1998 году он решился уйти из госбезопасности после 24 лет непрерывной работы.

Следующие перемены в судьбе Патрушева были связаны с быстрым карьерным ростом его коллеги по КГБ Владимира Путина. В 1997 году Анатолий Чубайс, знавший Путина по Ленинграду, посоветовал его Валентину Юмашеву — тогдашнему главе администрации президента. Путин пришел на позицию начальника главного контрольного управления президента и впечатлил Юмашева своей работоспособностью. В 1998-м Юмашев сделал его своим первым замом, а на освободившееся место пришел Патрушев.

Путин стал встречаться с Ельциным каждый день. К этому моменту от критики чекистов в ельцинской риторике не осталось и следа. «Оглядываясь назад, я вижу: в разоблачении преступлений органов безопасности мы чуть было не перегнули палку, — сетовал президент в 1997 году и развивал мысль дальше: — Сегодня в рядах наших спецслужб — подлинные патриоты своего дела. Эти люди работают не за славу и награды, а — не побоюсь этого слова — за идею».

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