Drawing on documents and memoirs in Russian and Arabic, this article tells the unknown story of Soviet-Egyptian cooperation in the early phases of the Yemeni Civil War, a war that broke out while much of the world's attention was focused on the Cuban missile crisis and the war between India and Pakistan. Egypt's fateful decision to intervene in the conflict was dependent on substantial Soviet backing, which strengthened the relationship between the USSR and Gamal Abdel Nasser's government in Egypt. In response to a plea from Nasser, Nikita Khrushchev authorized the military transport branch of the Soviet Air Force to embark on a clandestine airlift operation ferrying Egyptian troops into Yemen to shore up the new government there.