Talking about communism in Southwest Asia and North Africa involves reckoning with a formidable array of longings and anxieties. During the Cold War, Western scholars wrung their hands wondering whether the region would slip into the Soviet camp, while authoritarians jockeyed to paint themselves as anti-communists. As political Islam gained prominence in the 1970s, leftist observers both within and outside SWANA lamented the weakness of communist movements, imagining them as a preferable (perhaps even “rational”) alternative to Islamism. Despite the (seemingly) commonsense assumption that SWANA societies are too religious to embrace communist ideologies, the region is home to a range of possible communist trajectories. Some communist parties have stayed small, illegal, or marginalized (in Morocco and Saudi Arabia, for example), while others have enjoyed considerable prominence but then been repressed or decayed (Egypt’s original Communist Party). Still others (in Iraq and Sudan) have retained some political relevance over decades, and, of course, in South Yemen an explicitly Marxist movement came to—and held—state power. What accounts for the variation in these movements’ longevity, prominence, and success? Is it their organizational and ideological characteristics? The societies they operate in? Some feature of the regimes they challenge? Or the strength of labor movements upon which they can build? This paper offers an explicitly comparative perspective on the success of communist organizations across the region. As such, it speaks to a resurgent scholarly interest in the Arab left (e.g. Bardawil 2020; Ismael 2020; Guirguis 2022). Engaging with scholarship on ideology, parties, and repression across multiple disciplines, I argue that—contrary to common expectation—the strength of a country’s labor movement is not the best predictor of communist movement success. Drawing on two cases, the original Egyptian Communist Party (founded 1921) and the Sudanese Communist Party (founded 1946), I find the roots of these movements’ disparate trajectories in their different levels of ideological adaptability—stemming, in turn, from their different relationships with international communism. Moving beyond the standard juxtaposition of leftist and Islamist movements, I take intra-leftist variation seriously to explain why communism has maintained a better foothold in some countries than others.