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