The urgency of the strategic communication problems («the synchronization of words and deeds and how they will be perceived by selected audiences, as well as (b) programs and activities deliberately aimed at communicating and engaging with intended audiences, including those implemented by public affairs, public diplomacy, and information operations professionals» (White House, 2010, p. 2) keeps under the conditions of contemporary conflicts as high as never before. "War on Terror" which is conducted today by the West countries, became a part of their strategic communication which is oriented both on internal, and on external for the EU target audiences. At the same time discussion on a problem of terrorism has affected many people who felt themselves as victims of stereotypes, for example, certain Moslems groups in Europe. It has a negative impact on the image and reputation of law enforcement agencies of the European Union. The key roles in the European authorities' "War on Terror" interpretation play the supranational structures which are responsible for the regional security. In the present paper we make an attempt to analyze the basic problems of strategic communications of those European structures, caused by "War on Terror" contradictions. The author of the present paper tries to examine the following questions: To analyze the basic messages of the antiterrorist strategy in the Organization for Security and Co-operation in Europe (OSCE) documents. To characterize in brief the main problems and contradictions of the communication struggle against terrorism in the European Union. It is used in the paper both methodology of historical research, and methods of communication management which in system allow to track the development of the governmental strategic communication while the crisis spread all over the world.