This paper conceptualizes the evolution of the legitimacy of political violence. Utilizing a theoretical framework that operationalizes the use of social norms and social networks in optimizing recruitment by organizations of political violence, the paper deconstructs the legitimation process into two phases: the nascent stage where an initial cadre creates a foundation of legitimizing aims and a subsequent stage where this foundation is instrumental to the recruitment strategies and tactics of the organization. This theoretical framework is tested through an application to the case study of EOKA, the Greek Cypriot insurgent organization that engaged in an armed struggle against British colonial forces with the aim to unite Cyprus with Greece in the 1950s. The evidence from the case study is drawn from a new database based on interviews conducted with ranked officers and recruiters of the organization and a survey questionnaire of the members of the organization.