The meeting of Gamal Abdel Nasser and Zhou Enlai at the Asian-African Conference in Bandung, Indonesia, triggered three years of rapid development of ties between the People’s Republic of China and Egypt. Nasser’s decision in May 1956 to establish formal diplomatic relations with Beijing made Egypt the first Arab country and the first African country to recognize China’s Communist regime. Later that year, China’s outspoken backing of Nasser throughout the Suez Crisis further strengthened the special bond that was forming between the two countries. Yet as Chinese and Egyptian officials met again and again to proclaim their mutual admiration and unwavering support, these diplomatic efforts masked the fact that the most significant consequences of Sino-Egyptian relations were their ramifications within Chinese and Egyptian domestic politics. Both Mao Zedong’s and Nasser’s governments were young regimes still in the process of consolidating power and articulating a coherent guiding national ideology. The development of Sino-Egyptian relations afforded them an opportunity to refine the self-image they presented to their own constituents. As more and more scholars begin to pay attention to the history of China’s ties to Egypt, they should not overlook the profound ideological significance of this relationship as it was manifested within both societies. This paper analyzes the effects of developing relations between China and Egypt in the mid-to-late 1950s on two particular groups that had an inherent connection to both sides: Chinese Muslims and Egyptian leftists. Using primary sources in both Chinese and Arabic, as well as research in Chinese archives at both the national and local level, it demonstrates how the prevailing discourses about China and Egypt reinforced the nationalist credentials of Mao’s and Nasser’s governments. The government-run China Islamic Association and the central government in Beijing promoted Egypt, particularly during mass demonstrations at the height of the Suez Crisis, in a manner that reaffirmed Chinese nationalism and the legitimacy of the Chinese Communist Party (CCP). In Egypt, leftist commentators embraced the CCP in order to endorse the idea of “revolution” at a time when Nasser was beginning to articulate an ideological basis for his rule that also emphasized his revolutionary leadership. The similar experiences of China and Egypt as anti-imperialist countries allowed intellectuals and policymakers in both countries to present the other as a mirror in which to reflect their own societies.