Лебедь действует быстро. Он отдает приказ центральному пункту связи генерального штаба не передавать распоряжений бывшего министра обороны или его сторонников войскам. Кроме того, он связывается с командующими Московским военным округом и Воздушно-десантными войсками. В радиопослании он приказывает всем войсковым частям «уважать Конституцию». Кроме того, Лебедь постановляет, что любые «телеграммы соболезнования» Грачеву должны оплачиваться из собственного кармана. Это действует.

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

«Очень впечатляюще!» — комментирует один американский журналист изгнание команды вслед за Грачевым после вступления Лебедя в должность. В общем как в России, так и за рубежом преобладает положительная реакция: «Вместо нескольких тупых генералов у нас теперь один нормальный генерал — Лебедь», — пишет «Московский комсомолец». Российская частная телекомпания НТВ в сатирической программе «Куклы» изображает Лебедя «терминатором», который помогает президенту Ельцину отразить опасность в образе робота с чертами Зюганова, отсылая его в прошлое.

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

Тот факт, что положительные комментарии по поводу вступления Лебедя в новую должность в Кремле делают и многочисленные бывшие скептики или критики, не только говорит о приспособляемости оппортунистов, но и доказывает, насколько широко правительство все еще управляет прессой. На газетных снимках вместо сурового генерала теперь появляется достойный доверия политик со сносной внешностью — Лебедя сделали по всем правилам звездой телеэкрана. Газета «Коммерсант дейли» 23 июня 1996 года публикует психологический портрет Лебедя под названием «Необычная анкета». Лебедь должен закончить, по желанию, неполные предложения, например: «Когда я был ребенком, мой отец… учил меня жить по совести». «Я всегда хотел… летать высоко, не боясь разбиться». «Идеал мужчины я вижу в… Илье Муромце. Выждал — и сделал». Илья Муромец — один из главных героев-богатырей русского былинного эпоса. По преданию, он много лет не мог передвигаться, пока проходивший мимо паломник не попросил у него воды и не заставил его встать и самому выпить первый глоток. После второго глотка Илья Муромец почувствовал себя таким сильным, что был в состоянии «соединить землю и небо, если бы они были окружены издавна железным кольцом». Паломник предостерег его от третьего глотка, так как после него он стал бы таким сильным, что земля не смогла бы его больше носить.

Сразу после первого тура выборов ответственный за связь с прессой американского министерства иностранных дел Николас Бернс на брифинге сказал: «Мы увидели здесь реального политика. После первого тура генерал Лебедь стал главой Совета безопасности в правительстве Ельцина. Важный пост не только для внешнеполитических интересов, но и для внутренней безопасности самой России… Лебедь в своей кампании сконцентрировал внимание на таких проблемах, как коррупция и преступность, и это находит большой резонанс в России. Это, кажется, хорошо как для президента Ельцина, так и для генерала Лебедя. Мы ждем, как и в последние годы, дальнейшего сотрудничества и продолжения реформ…

Другой интересный кандидат, Григорий Явлинский, важный проводник реформ. Я полагаю, он еще будет влиятельным… В высшей степени достойный внимания человек».

НАТО реагирует в общем положительно на назначение Лебедя в Совет безопасности: «Что хорошо для России, хорошо и для нас», — говорит Крис Доннелли от имени генерального секретаря Соланы. Доннелли обосновывает это тем, что «Североатлантическому Союзу нравится желание Лебедя сделать российскую армию сильной и управляемой. Нельзя, чтобы она была слабой и разрываемой противоречиями. Это просто опасно».

«Тревожным» считает итальянская «Стампа» назначение Лебедя в Кремль. Для французской публицистки Анны Керлох Лебедь «русский Пиночет», а портреты Дуайта Эйзенхауэра и де Гол-ля в предвыборном штабе Лебедя выполняли лишь функцию алиби.

Майкл Гордон из «Нью-Йорк Таймс» сравнивает Лебедя с Колином Пауэллом: «У него прагматичная программа, и он называет ее «идеологией человека здравого ума»», — успокаивает журналист скептиков и сразу напоминает о том, что Лебедь предложил Чечне «исключительно демократический выход». Наконец Мартин Малиа, историк из университета Беркли в Калифорнии, комментирует 17 июня: «Лебедь добился такого замечательного результата, потому что он не запятнан ни позорным прошлым коммунистов, ни коррупцией властных структур вокруг Ельцина — он свеж, чист, честен, прямолинеен и относительно молод… Он не просто националист, которым он перестал быть, возможно, в Молдавии. Он за рыночную экономику и, несмотря на его восхищение генералом Пиночетом, он и за конституционное правительство. Что касается войны в Чечне, он не представляет позицию Ельцина, но его честное неприятие коммунизма сильнее, чем его критическое отношение к президенту. И когда он говорит о «сильной, достойной России», это означает защиту интересов русских в «ближнем зарубежье», называемых несправедливо гражданами второго сорта…

Между прочим, он, видимо, скорее стремится к союзу грех славянских республик Беларуси, Украины и России. Будет ли он бряцать оружием? Конечно, нет. Лебедь, по существу, не тот человек, который делает политику военными средствами — тем более, что он знает средства и техническое положение России… Избиратели Лебедя вряд ли пойдут к Зюганову во втором туре выборов, потому что Зюганов достиг границ своих возможностей. Таким образом Ельцин выиграет…