Несмотря на то, что Йемен стал первым арабским государством, заключившим договор с СССР в 1928 году, отношения двух стран были лишены какой-либо содержательной части, пока за дело не взялся Хрущев. Как и в других случаях, посредником был Насер, и все вертелось вокруг поставок советского оружия . Насер, фактически играл роль регионального дилера советского оружия, и наградой него были не деньги, но влияние. С советской точки зрения, вооружение йеменцев несло с собой преимущества противостояния с британской колонией в Адене. Каир всячески раздувал советскую враждебность к британскому присутствию на Ближнем Востоке – задолго до начала йеменской войны. Более важным фактором была постепенная трансформация традиционного северного соседа Йемена – Саудовской Аравии из традиционного союзника в главного врага. Вооружая йеменцев, Насер влиял на происходящее в мягком подбрюшье Саудовской Аравии, превращавшейся во все более проблемного конкурента в регионе.
В 1956 году Насер осуществил сложную интригу, с целью убедить своих советских друзей в злонамеренности Саудов. В то время имам Ахмед обратился К СССР с просьбой о поставках оружия. Советский посол в Каире, Евгений Киселев, поделился с Насером своими опасениями – йеменский режим нестабилен, а поставки могут разозлить Саудов. Насер, в свою очередь, рассказал послу о том, что все его попытки убедить короля Сауда в безопасности установления связей с СССР не привели к положительным результатам. Насер выразил полную поддержку советским планам продажи оружия Йемену. Это могло показаться советским товарищам несколько странным – всего за три месяца до этого Египет подписал пакт о взаимной обороне с Йеменом и Саудовской Аравией. На деле Насер уже планировал свою партию по подрыву королевства. Йемен сам по себе не имел значения – но он был необходимой частью плана из-за саудовского соседства.
С благословения Насера, сделка была заключена во время визита наследного принца Мухаммеда аль-Бадра в Москву в июле 1956 года. Вооружения – устаревшие танки, бронетранспортеры, вертолеты, самолеты, легкая артиллерия и стрелковая оружие, были торжественно провезены перед ликующими толпами в Худейде спустя несколько месяцев после окончания визита принца. Сделка укрепила престиж аль-Бадра, но, в то же время, приблизила кончину имамата, вооружив и без того проблемную и беспокойную йеменскую армию. Вслед за оружием в Сану была отправлена советская военная миссия. За нею последовала египетская военная миссия. Делегации договорились о разделе сфер ответственности. Русские занимались уходом за вооружениями и технической подготовкой, египтяне обучали йеменцев премудростям тактики и стратегии в только что открывшейся военной академии в Сане.
