Лебедь предотвращает возможное возвращение экс-министра, уволив генералов, близких Грачеву, обвинив в участии в заговоре: генерал-полковника Виктора Барынкина, заместителя начальника генерального штаба; генерал-полковника Анатолия Ситнова, руководителя отдела; генерал-полковника Дмитрия Харченко, начальника отдела международного военного сотрудничества; заместителей начальника генерального штаба генерал-полковника Анатолия Богданова и Вячеслава Жеребцова; генерал-полковника Валерия Лапшова, руководителя секретариата министерства обороны; генерал-лейтенанта Владимира Шуликова, кроме того, начальника управления воспитательной работы министерства обороны генерал-лейтенанта Сергея Здорикова. Позже добавляются заместители секретаря Совета безопасности Александр Трошин и Владимир Рубанов, который подал прошение об отставке после того, как высказал критическое отношение к Лебедю. Одновременно с чисткой, проводимой Лебедем, и президент Ельцин увольняет трех человек: Олега Сосковца, первого заместителя главы правительства, отвечавшего за военно-промышленный комплекс, директора Федеральной службы безопасности генерала армии Михаила Барсукова, а также руководителя службы охраны президента генерал-лейтенанта Александра Коржакова. Свои полномочия должен сдать и бывший советник президента по вопросам безопасности Юрий Батурин, место которого занял Лебедь. Олега Лобова Ельцин назначает вице-премьером. Он, кроме того, является уполномоченным президента в Чечне.
«Очень впечатляюще!» — комментирует один американский журналист изгнание команды вслед за Грачевым после вступления Лебедя в должность. В общем как в России, так и за рубежом преобладает положительная реакция: «Вместо нескольких тупых генералов у нас теперь один нормальный генерал — Лебедь», — пишет «Московский комсомолец». Российская частная телекомпания НТВ в сатирической программе «Куклы» изображает Лебедя «терминатором», который помогает президенту Ельцину отразить опасность в образе робота с чертами Зюганова, отсылая его в прошлое.
Популярный публицист Александр Минкин анализирует ситуацию в Кремле: Ельцин уже несколько лет обманывал народ, однако был избран «как меньшее зло» — большей частью теми, «которые, став неимущими, почувствовали себя лишними в результате новой свободы, от которой имели выгоду до сих пор только полукриминальные элементы». Минкин констатирует, что Ельцин действовал «не из политического инстинкта», а «из страха», если он пошел на альянс, так как он ему срочно был нужен, как и Зюганову, чтобы победить. Минкин считает Зюганова «внешним врагом» для правительства Ельцина, а Явлинского — «внутренним», он, по существу, принадлежит к тому же лагерю, однако стоил Ельцину голосов. Наконец, Минкин устанавливает — и в этом ключ к дальнейшему развитию Лебедя, — что самому президенту нужно было его переизбрание меньше, чем его окружению, так как его поражение означало бы для них конец: «Сегодня маленькие боги, завтра они были бы обыкновенными посредственными гражданами. Сегодня в Кремле — завтра в камере в Лефортово. У них нет будущего — только их настоящее. Оно позволяет им распоряжаться миллиардами рублей, армией, тайной полицией и владеть роскошными дворцами…».
Тот факт, что положительные комментарии по поводу вступления Лебедя в новую должность в Кремле делают и многочисленные бывшие скептики или критики, не только говорит о приспособляемости оппортунистов, но и доказывает, насколько широко правительство все еще управляет прессой. На газетных снимках вместо сурового генерала теперь появляется достойный доверия политик со сносной внешностью — Лебедя сделали по всем правилам звездой телеэкрана. Газета «Коммерсант дейли» 23 июня 1996 года публикует психологический портрет Лебедя под названием «Необычная анкета». Лебедь должен закончить, по желанию, неполные предложения, например: «Когда я был ребенком, мой отец…