The historiography of the Cold War has generally overlooked issues of ethnicity and immigration. By focusing on the case of one left-wing migrant from Cyprus, this article retrieves from historical obscurity the battles for citizenship rights that many migrants faced in Cold War Australia. The article throws light on the serious implications that existed for those who fell foul of the security establishment and argues that, on the principle of deportation, ASIO’s position was more draconian than that of the Department of Immigration.