The use of information and communication technologies in tourism has been a rapidly expanding field. However, most of the relevant applications relate to the transaction processing systems than decision support systems, which are designed to handle procedural tasks, such as airline and hotel reservation systems or destination management systems. These computer tools are of little support in decision situations involving uncertain, unknown or conflicting information while computerised systems to support sustainable tourism policy making are rather absent. Different decision support approaches are explored to identify the one that better matches sustainable tourism policy making needs. Sustainable tourism policy making is perceived as a complex domain involving various issues which have to be managed simultaneously with often competing goals. It is argued here that soft decision support systems, based on knowledge capturing and representation in the form of mental models could have an important contribution to the improvement of sustainable tourism policies. A cognitive mapping method to elicit, analyse and represent the mental models that policy makers in Greece hold for sustainable tourism policies is presented. Findings are discussed to reveal the complexity of the domain being investigated and highlight the contribution of mental models to the development of a decision support system to assist policy making for sustainable tourism.