If we conceptualise society as a complex system, we may observe that its complexity arises from a multitude of its constituent elements – individuals, groups, organisational units, etc. - and from a multitude of their interconnections. Moreover, these interrelations are themselves complex in a sense that the “state” of each element depends not only on its previous state, but also on a complex combination of previous states of many other elements. Yet more, humans build their own perceptions of various dependencies between a social system’s elements, which affect further development of these dependencies, which, in turn, may influence the very perceptions. We argue that this complex-systems-view-of-society may help us better understand the often-cited “ambiguity” of the notion of security, as well as the shifts of foci of security concerns, such as the one that marked the ending of the Cold War. While, during the Cold War period, the focus of security concerns was at the national or the state level, after the end of the Cold War, the focus moved to the sub-state, the group and the individual level, as well as to the supra-state and the global level. What had previously been regarded as “monolithic” national security, now became a more diffuse and ambiguous concept with multiple meanings. The task of an analyst in those new circumstances became much harder. Instead of “monolithic” states with mutually conflicting, but structurally similar national interests, analysts of the post-Cold-War world have been confronted with much greater heterogeneity of identities and interests of multitudes of individual and group actors. In contrast with a few relatively simple inter-dependencies between the Cold War states, based mostly on mutual balance of military power, multiple interindividual and intergroup ties have spanned multiple dimensions, being subject to incessant commotion and change. In contrast to passive, inanimate states, the “new security environment” abounds with perceptive human subjects, capable of influencing current and constructing ever new, yet unanticipated realities. The new security environment requires new, more adequate methods of studying and analysis. We argue for the methods of complex systems research to provide these much needed new tools. The arguments that we provide are general, pointing to the more concrete examples of application of complex systems methods to particular security challenges and opportunities, which are further discussed as part of the remaining contributions to this workshop.