На состоявшемся в тот вечер чрезвычайном заседании Министерства внутренних дел Серов был представлен как новый советский советник, причем имя его названо не было. Делая ударение на каждом слове, Серов сообщил собравшимся: «Фашисты и империалисты выводят свои ударные силы на улицы Будапешта. И все же находятся товарищи в вооруженных силах вашей страны, которые сомневаются, применять ли им оружие.» Шандор Копачи, начальник будапештской полиции, который вскоре перешел на сторону борцов за свободу, ответил с нескрываемым презрением: «Видимо, товарищ советник из Москвы не успел изучить обстановку в нашей стране. Надо сказать ему, что на демонстрацию вышли не фашисты и прочие империалисты, а студенты университетов, лучшие сыны и дочери рабочих и крестьян, цвет нашей интеллигенции, и они требуют осуществления своих прав, хотят выразить сочувствие полякам и проявить с ними солидарность.» Четверть века спустя Копачи все еще не мог забыть долгий испепеляющий взгляд стальных глаз Серова.
В тот же вечер 23 октября Герэ с согласия советского руководства назначил Надя премьер-министром. Одновременно он обратился за братской помощью советских войск, находящихся в Венгрии, в борьбе с угрозой контрреволюции. На следующее утро, ошибочно предположив, что рабочие не поддержат студентов, Красная Армия с помощью АВХ предприняла первую попытку задушить революцию. Уличные бои, длившиеся несколько дней, убедительно продемонстрировали, на чьей стороне были на самом деле симпатии рабочих.
25 октября Герэ на посту Первого секретаря партии сменил Янош Кадар. Вместе с Надем он затем объявил, что переговоры о выводе советских войск начнутся, как только будет восстановлен порядок. В течение нескольких дней, как потом признал Хрущев, Кремль пребывал в нерешительности: «применить военную силу» или «уйти из Венгрии». «Не знаю, сколько раз мы принимали то одно, то другое решение.» Подозревая наличие империалистического заговора, Серов приказал примерно двадцати нелегалам КГБ, жившим на Западе под вымышленными именами и с фиктивным гражданством, прибыть в Венгрию, доложить обстановку и при необходимости устраивать провокации, чтобы помочь оправдать военное вмешательство. Та же тактика была использована и в Праге в 1968 году.
Тем временем события в Будапеште развивались все быстрее и быстрее. 29 октября была упразднена ненавистная АВХ, повинная в гибели сотен демонстрантов и потерявшая несколько своих сотрудников, которые были растерзаны толпой. 30 октября эмиссары Кремля Микоян и Суслов согласились вывести советские войска и обсудить выход Венгрии из Организации Варшавского Договора. Вскоре после полудня Надь обратился по радио к народу, объявив, что он формирует новое многопартийное правительство: «В интересах дальнейшей демократизации жизни страны кабинет отменяет однопартийную систему и переводит управление страной на основу демократического сотрудничества между коалиционными партиями в том виде, в каком они существовали в 1945 году.» До 30 октября Москва возлагала на Надя большие надежды в сдерживании контрреволюции. Но с этого момента Кремль втайне начал готовить его свержение.
Ввести правительство Надя в заблуждение относительно истинных намерений советского руководства предстояло Юрию Андропову. Один молодой советский дипломат в Будапеште позже вспоминал с восторгом, что Андропов первым «раскусил» Надя и ни на один миг не терял самообладания на всем протяжении разразившегося впоследствии кризиса: «Он был абсолютно спокоен, даже когда кругом свистели пули и когда все мы чувствовали себя в посольстве, как в осажденной крепости.» Рано утром 1 ноября Надю сообщили, что части Красной Армии пересекли венгерскую границу, в то время как другие советские части выходят из Будапешта. Андропов неоднократно заверял Надя, что вывод войск идет строго по плану, а те войска, которые были введены в Венгрию, будут только обеспечивать безопасность частей, которые выводятся. Надь объявил о выходе Венгрии из Организации Варшавского Договора, провозгласил венгерский нейтралитет и обратился в ООН с просьбой включить венгерский вопрос в повестку заседаний организации. На следующий день, 2 ноября, венгерское правительство заявило Советскому Союзу официальный протест по поводу повторного ввода советских войск и поставило в известность о происходящем ООН. Продолжая убеждать Надя, что вывод войск не прекращается, Андропов вместе с Кадаром тайно начал готовить заговор с целью свержения правительства Надя. Кадар наверняка действовал под нажимом: он еще не забыл, как сам сидел и подвергался пыткам с 1951 по 1954 год, к тому же Андропов пригрозил, что если он откажется сотрудничать, вернется Ракоши.