Еще одним особенно важным шагом для венгерской дипломатии стало сделанное в августе 1988 года публичное заявление о том, что предстоящее международное соглашение о сокращении обычных вооруженных сил в Европе должно распространяться на войска, размещенные в Венгрии уже на первом этапе. Однако такая возможность была возможна только в том случае, если Венгрия будет включена в состав Центрально-Европейского театра военных действий, что ни в коем случае нельзя было считать само собой разумеющимся. Поскольку Варшавский договор имел решающее преимущество в этом регионе, в интересах организации было сохранить Венгрию на южноевропейском театре военных действий, чтобы улучшить показатели соотношения, где НАТО имела преимущество. Однако в этом регионе именно западные союзники должны были пойти на значительные сокращения, поэтому венгерские усилия потерпели бы полное фиаско. Хотя венграм удалось заручиться поддержкой советского руководства в отношении своей позиции, различные интересы других стран-членов оказались существенным фактором неопределенности даже весной 1989 года.
Для советского поведения было характерно, что Горбачев положительно отреагировал на заявление премьер-министра Миклоша Немета во время его визита в Москву в марте 1989 года о том, что венгерское правительство решило сократить свою армию на 30-35 процентов к 1995 году. Он "всего лишь" попросил держать это в секрете, поскольку обнародование этого решения значительно ослабило бы позиции Варшавского договора на переговорах о сокращении вооружений в Вене.
Если сокращение национальных военных расходов было продиктовано в первую очередь экономическими соображениями, то призыв к выводу советских войск, размещенных в Венгрии, преследовал в основном политические цели. Вопрос был поднят в связи с заявлением СССР в 1988 году о том, что Советский Союз выведет все свои войска с чужой территории к 2000 году. Поэтому уже в августе и сентябре 1988 года венгерские эксперты по внешней политике пытались убедить своих советских партнеров в том, что скорейший вывод советских войск будет иметь для Венгрии весьма положительные политические, моральные и экономические последствия.
Необходимость частичного одностороннего сокращения уже была предложена и Советами, в результате чего в декабре 1988 года было объявлено о выводе из Венгрии около десяти тысяч советских военнослужащих и их технического оборудования, что и произошло в апреле-мае 1989 года. Подобный частичный вывод уже имел место ранее, в 1958 году, но он не привел к каким-либо значительным изменениям. Таким образом, реальный вопрос заключался в том, сможет ли венгерское руководство положить конец советской оккупации страны, которая была основной претензией для большинства населения на протяжении последних четырех десятилетий. Другой важный вопрос заключался в том, сможет ли ВСП в достаточной степени воспользоваться этим в период политических преобразований.
В результате настойчивой деятельности венгерских внешнеполитических деятелей, которые последовательно пытались укрепить элементы национального суверенитета, корректируя при этом свой курс действий в соответствии с советскими интересами, в середине мая 1989 года Москва дала понять, что на следующем заседании ПКК ЗП, которое должно было состояться в Бухаресте, Горбачев будет готов начать переговоры с венгерской делегацией о полном выводе советских войск. Настоящие переговоры наконец состоялись, когда в конце июля Москву посетили Карой Груш и Рецьо Ньерс, генеральный секретарь и председатель ВСП соответственно, и Горбачев согласился издать меморандум, в котором говорилось, что при соответствующих международных условиях уже осуществляемый отвод войск может привести к полному выводу советских войск. В августе начались дальнейшие переговоры между двумя правительствами, и в результате 10 марта 1990 года в Москве последним венгерским коммунистическим правительством было подписано соглашение о выводе примерно пятидесяти тысяч советских войск к 30 июня 1991 года. (Тем временем в ноябре 1989 года по просьбе премьер-министра Миклоша Немета из Венгрии в обстановке полной секретности были вывезены советские ядерные боеголовки, размещенные в стране Советской Армией с конца 1960-х годов). Процесс вывода не обошелся без споров, но Советы уложились в срок: последний советский солдат покинул страну 19 июня 1991 года. Таким образом, через год после прихода к власти первого свободно избранного правительства Венгрия полностью восстановила свой суверенитет.