Ельцин хотел заменить Кириенко своей старой верной рабочей лошадкой Виктором Черномырдиным, известным своими малапропизмами в духе Йоги Берра, такими как: «Ситуация совершенно беспрецедентная – опять та же самая история!» и «Лучше я не буду говорить, иначе я что-нибудь скажу…», – однако Дума не позволила назначить его на эту должность. В качестве компромисса, приемлемого для большинства депутатов, в сентябре эту должность принял Евгений Примаков, бывший руководитель СВР (Службы внешней разведки), с января 1996 года служивший в качестве министра иностранных дел. Вначале Примаков отклонил предложение Ельцина, но, как он позже высказался в своих мемуарах «Годы в большой политике», при выходе из кабинета Ельцина он столкнулся с «Таней и Валей», которые убедили его принять предложение. «На мгновение разум отступил, и чувства взяли верх», – писал он. Как показало время, Примаков, надо отдать ему должное, был слишком независимым и пытливым, и меньше чем через год его сместили с поста.

Двадцатого ноября Путин услышал новость о том, что в Санкт-Петербурге была убита Галина Старовойтова. На доктора наук Старовойтову и ее помощника Руслана Линькова напали двое мужчин на лестнице ее жилого дома. 52-летняя женщина-демократ получила три пули в голову и умерла на месте происшествия. Линькову тоже выстрелили в голову, но он выжил. Бросив оружие на лестнице, убийцы скрылись на поджидавшем их автомобиле.

Доктор наук Старовойтова была неоднозначной фигурой, у которой было много врагов. Во время своих частых поездок на Запад она высказывала предостережения о том, что реформаторов России атакуют влиятельные группы, «стремящиеся восстановить старую экономическую и политическую систему» и использовать ностальгию по коммунистическим временам к своей выгоде. В свое время Ельцин назначил ее своим советником по вопросам этнических меньшинств. В 1994 году у них возникла ссора вследствие разногласий по чеченскому вопросу, но затем они достигли консенсуса. Проблема для врагов доктора психологии Старовойтовой состояла в том, что она была неподкупна. Она планировала представить Думе доказательства коррупции коммунистов и только что объявила, что будет баллотироваться на должность губернатора – причем ее соперником был давний противник Ельцина Владимир Жириновский, националистический лидер, пытавшийся, в соответствии с ее обвинениями, построить «преступную диктатуру», – но была убита… Одним из излюбленных объектов ее внимания была российская армия. «Наши вооруженные силы не несут ответственности перед гражданским обществом, и у них нет обязательств даже по отношению к Президенту», – отстаивала она свою позицию. Ельцин высказал предложение о том, чтобы она возглавила Министерство обороны, но она отшутилась, сказав, что Россия пока что не готова к министру обороны в юбке.

Услышав новость об убийстве Старовойтовой, Ельцин назвал ее своим «самым близким соратником». Он послал министра внутренних дел Сергея Степашина, ветерана службы безопасности России, в Санкт-Петербург с целью найти ее убийц. Главными подозреваемыми были наемные убийцы, действовавшие по заказу ГРУ, военного управления внешними вооруженными силами России. Расследование убийства проходило под личным руководством Сергея Степашина, бывшего главы ФСБ и впоследствии премьер-министра России. В июне 2005 года двое наемных убийц, Юрий Колчин и Виталий Акишин, были признаны виновными и приговорены соответственно к 20 и 23 годам тюремного заключения. Несколько других подозреваемых до сих пор находятся в розыске в связи с расследованием убийства Старовойтовой, которое было возобновлено в 2009 году. Тем временем Путин начал восьмой по счету процесс реорганизации ФСБ в течение того же количества лет, которое потребовалось на этап борьбы за развитие экономики. Он упразднил два отдела (экономической контрразведки и защиты стратегических объектов) и уволил приблизительно 40 генерал-лейтенантов и генерал-майоров и около трети основного штата, сократившегося с 6000 до 4000 человек. Поскольку удар обрушился, главным образом, на тех, кто приближался к пенсионному возрасту или уже достиг его, многие утверждали, что федеральная служба лишилась своих самых опытных сотрудников, и Путин действительно был намерен избавиться от тех, кто имел наиболее прочные связи со старой советской властью.

Это было для него трудным временем, усугубившимся смертью его любимой матери Марии в конце 1998 года после долгой борьбы с раком. Он взял отпуск, чтобы быть рядом в ее последние дни. Хотя Путин закрыл ей глаза на смертном ложе, в своем характерном стиле он не проявлял сильных эмоций. Если он и плакал, то делал это без свидетелей.

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

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

Одновременно Юрий Скуратов начал расследовать дело Павла Бородина, который, как утверждалось, брал взятки в крупном размере у швейцарской машиностроительной компании «Мабетекс», выполнявшей многомиллионные реставрационные работы в Кремле. Скуратов, сын работника милиции, начал свою карьеру в качестве профессора права в родном регионе Ельцина. Он поддерживал Ельцина как местного главу коммунистической партии, а затем как демократического реформатора. В 1989 году он вступил в штат юридического отдела Центрального комитета коммунистической партии в Москве. К 1991 году он уже являлся членом команды Ельцина в качестве советника КГБ и затем подготовил проект Конституции 1993 года совместно с Анатолием Собчаком, который также был объектом его внимания.

Когда в октябре 1995 года его назвали главным прокурором, оппозиция в Думе поддержала его как политически нейтральную фигуру. Имущественное управление Бородина предоставило ему дачу в предместьях Москвы, он разъезжал на бронированном «Мерседесе». Однако к 1999 году широкой публике было хорошо известно, что Скуратов, несмотря на браваду и широкие полномочия, был не в состоянии ни предъявить иск ключевым фигурам, вовлеченным в коррупцию, ни расследовать заказные убийства политических деятелей и прочих видных людей.

В интервью газете «Нью-Йорк Таймс» Скуратов утверждал, что разочаровался в режиме Ельцина после выборов 1996 года, во время расследования дела Лисовского и Естафьева. Он вскоре понял, что отрицание виновности кремлевских деятелей было ложью, тогда как главные правительственные советники оказывали на него давление, вынуждая его прекратить расследование. Сейчас же он утверждал, что имеет предоставленное офисами «Мабетекс» в Лугано (Швейцария) документальное подтверждение того, что компания предоставила кредитные карты Ельцину и его двум дочерям, Татьяне Дьяченко и Елене Окуловой. Наличие этих документов означало, что компания «Мабетекс» оплачивала покупки, совершаемые за счет этих карт, что составляло десятки тысяч долларов.

Расследование дела только начало продвигаться, как обнаружилась уязвимость Скуратова. На камеру был снят похожий на него человек, развлекавшийся с двумя проститутками в сауне, по-видимому, в нетрезвом состоянии. Данное видео впервые показали по государственному телеканалу РТР. Это вызвало сенсацию; кадры из видеоролика были опубликованы в большинстве российских газет. То, что на видео присутствовал сам Скуратов, так и не было доказано, и он утверждал, что его опознали ошибочно и что его враги в Кремле намеревались очернить его репутацию. Хотя никто не мог определить, кем был снят этот ролик, как и то, кто на самом деле на нем присутствовал, имелись все признаки того, что это ловушка ФСБ. Путин выступил с подтверждением того, что обнаженный круглолицый человек на видео и есть генеральный прокурор. В тот день, когда были совершены рейды на «Сибнефть», Ельцин, по слухам, вызвал Скуратова на свою дачу в Горки-9, где к удивлению генерального прокурора рядом с Президентом находился также Путин. В присутствии Путина Ельцин «предложил» Скуратову немедленно написать прошение об отставке. У прокурора не оставалось выбора. Получив документ, Ельцин засмеялся и пожал руку Путина, что усугубило унизительность ситуации.