Кремль требовал от Степашина решительных действий, но премьер-министр медлил. Во время первой Чеченской войны он руководил пришедшей на смену КГБ Федеральной службой контрразведки (в настоящее время ФСБ), и не снимал с себя вины за многочисленные жертвы среди военнослужащих и мирного населения. Особенно мучительными были воспоминания о трагическом инциденте в Буденновске, когда отряду исламистов удалось беспрепятственно миновать множество блок-постов и устроить кровавую бойню в небольшом ставропольском городке. Операция по освобождению заложников, удерживаемых террористами во главе с Басаевым в здании больницы, окончилась полным провалом, и не в последнюю очередь из-за ведомственной неразберихи. Бойцам российских спецподразделений пришлось идти на штурм здания по пристрелянному открытому пространству под непрерывным огнем гранатометов, автоматов и крупнокалиберных пулеметов. Тогда Степашин подал в отставку. В свою бытность министром внутренних дел он попал в аналогичную ситуацию. Летом 1998 года ваххабисты взяли под контроль два села в центральной части Дагестана и принялись интенсивно возводить там военные укрепления. Желание избежать кровопролития было так велико, что Степашин даже распорядился отвести подальше подчиненные ему войска. Он искренне полагал, что для мирной нейтрализации чеченского сепаратизма достаточно будет установить на границе «санитарный кордон». В преддверии президентских выборов он также не хотел рисковать и сперва предлагал просто взять бандформирования в плотное кольцо. Однако резко обострившаяся обстановка на всем Северном Кавказе требовала радикального решения проблемы. После отмены результатов выборов политический кризис в Карачаево-Черкессии достиг апогея, и республика оказалась на пороге гражданской войны. Возвращение ингушских беженцев в места их прежнего проживания в Северной Осетии грозило вылиться в новый вооруженный конфликт. Отказ Грузии от военного сотрудничества со странами СНГ и обращение этой бывшей союзной республики к США с просьбой оказать содействие в реформировании вооруженных сил по западному образцу привели к дальнейшему ухудшению ее отношений с Россией. После долгих колебаний Степашин, наконец, приказал начать наступление на позиции «бойцов ислама».
Российский политический бомонд в очередной раз занялся выявлением подлинных причин войны и поисками ответа на вопрос: откуда у боевиков самое современное вооружение? Куплено ли оно на деньги, вырученные от торговли наркотиками и людьми? Финансируют ли их страны исламского мира, стремящиеся распространить свое влияние на заселенную в основном мусульманами часть постсоветского пространства? Ведь на стороне сепаратистов сражалось много наемников из Пакистана, Афганистана и Саудовской Аравии. Не исключено, что конфликт намеренно разжигали государства, чьи региональные и геополитические интересы непосредственно связаны с обнаруженными на дне Каспийского моря богатыми залежами нефти и планами строительства трубопровода для ее перекачки в Турцию. Или же обострение ситуации спровоцировано влиятельными преступными группировками, давно пустившими корни во властных структурах и использовавшими территорию Чечни для нелегального бизнеса? Высказывались даже предположения, что вина за нагнетание напряженности в Северокавказском регионе целиком лежит на неких близких к Кремлю таинственных личностях, якобы они замыслили таким образом создать предлог для введения чрезвычайного положения и отмены выборов. Вторжение чеченцев в Дагестан вновь сделало актуальной проблему сохранения единства Российской Федерации.
После возвращения в конце июля из зоны боевых действий Степашин с горечью констатировал, что после Чечни Россия может потерять и Дагестан. Правда он тут же поспешил добавить, что «не боится взять на себя ответственность», но у Ельцина уже лопнуло терпение. Премьер-министра срочно вызвали в Кремль. В кабинете рядом с президентом сидел первый вице-премьер Аксененко, неизменно представлявший в правительстве интересы Березовского. Вслед за Степашиным в президентский отсек торопливо вошел Владимир Путин, одновременно возглавлявший ФСБ и Совет безопасности постепенно превращающийся в один из высших органов государственной власти. Ельцин коротко сообщил Степашину о его увольнении и, чтобы подсластить пилюлю предложил ему должность секретаря Совета безопасности. Степашин отказался и, пройдя мимо двух охранников, медленно побрел по идеально ровному и чистому кремлевскому двору к ожидавшему его черному бронированному автомобилю, оснащенному системой специальной связи. Кое-кто даже утверждал, что видел у него на глазах слезы. На заседании правительства бывший премьер-министр стоял с застывшим, почерневшим лицом и, казалось, еще не совсем оправился от шока. Тем не менее, он нашел в себе мужество высказать слова признательности в адрес президента: «Борис Николаевич мальчишкой ввел меня в политику. Я ему всю жизнь буду благодарен и навсегда останусь с ним».