None-state actors like Al Qaeda and its associated movements have given new dimension to the international terrorism and security after the Cold War. The 11 September 2001 attacks, attacks in Bali (2002), London (2004), Madrid (2005), Mumbai (2009) and Moscow (2010) attest that these non-state actors’ agenda has become global, apocalyptic and critical infrastructure focused. Connections to Al Qaeda by some Muslim groups and individuals from South-East Europe in an age of globalization, corrupt transitions, violent Yugoslavia conflicts and active support to the Global war on terror, rise serious concerns to the safety of the critical infrastructure in the region of South-East Europe (SEE). Like the rest of the South-East European’s countries, Macedonia misses effective strategy that will reduce the risks to critical infrastructure posed by Al Qaeda and its associated movements. Centralized planning and decentralized execution focused not just on immediate threats, but also on preventive measures could ensure effective critical infrastructure protection form Al Qaeda and its associated movements. To be fully effective Macedonia and South-East European’s governments need to coordinate, facilitate and stimulate all stakeholders involved in critical infrastructure protection.