During recent years the security environment has become more unpredictable and complex. The armed forces face a broader spectrum of tasks, with an increased focus on low intensity conflicts. The inherent uncertainty and complexity of these operations are indeed a challenge for long-term planning as well as for direct OR support to military operations. The first problem is to define the problems. Problem structuring methods (PSM) such as Soft Systems Methodology (SSM) are a useful approach for discussing and agreeing on which problems to address. The next challenge is how to include uncertainty in the analysis models and evaluations. Use of scenarios is one common approach to explore uncertainties in the future security environment. Uncertainties and inaccuracy related to model parameters and human decision making may be represented by, for instance, probability distributions and fuzzy sets. Decision making related to complex problems usually includes more than one decision criterion. Various methods for multi-criteria decision analysis offer different approaches for modelling preferences and to rank alternatives. We believe that combining different OR methods – soft and hard – are a fruitful approach to deal with complexity and uncertainty. Thus, we have developed a framework of methods that combines elements of SSM, elements of scenario planning, value modelling and a multi-criteria model for evaluation and prioritizing of decision alternatives. This framework is currently applied in a case study addressing the effectiveness of the Norwegian oil-spill preparedness system.