Following the Kuomintang's party-state's retreat to Taiwan in December 1949, the party-state intensified its post-colonial program of eradicating all traces of the Japanese colonial period, implementing in their place a powerful and penetrating sino-centric nation-building program. This nation-building effort was not only aimed at socializing Taiwanese society into the regime's ideal master narrative on the meaning of Chinese nationhood, but also, using the rhetoric of anti-communism and national resurrection, sought to establish the KMT's political and cultural legitimacy on the island. This paper addresses the historical background and implementation of the party-state's nation-building agenda on Taiwan through analysis of the KMT's "communist spy" rhetoric, and the discursive construction of dichotic symbolic classificatory schemes, such as us/enemy, orthodox/heterodox, and good/evil. Using primarily qualitative narrative analysis of newspapers and official party-state documents from the 1950s, this work attempts to address the myriad of ways in which images and portrayals of the "evil communists" and "communist spies" were produced and reproduced in written KMT discourse. A few typical examples of communist bandit/communist spy narrative are examined, and it is suggested that, through establishing classification schemes by which to identify "communist spies", the KMT regime was able to establish an atmosphere of mutual surveillance among Taiwanese. This, it is argued, played a decisive role in the subsequent establishment of KMT social control and political/cultural hegemony of Taiwan in the post-colonial period.