Spatial decision support is one of the central functions ascribed to Geographical Information Systems (GIS). One of the foci of developing decision support capabilities of GIS has been the integration of maps with multiple criteria decision models. Progress in this area has been slow due to a limited role played by maps as decision support tools. In this paper we present new prototype spatial decision support tools emphasising the role of maps as a source of structure in multiple criteria spatial decision problems. In these tools the role of map goes beyond the mere display of geographic decision space and multicriterion evaluation results. Maps becomes a 'visual index' through which the user orders decision options, assigns priorities to decision criteria, and augments the criterion outcome space by map-derived heuristic knowledge. As the additional means of structuring multicriterion spatial decision problems we present an experimental use of data mining, integrated with dynamic maps and multiple criteria decision models, in order to reduce a problem's dimensionality. We conclude the paper with future research directions emphasising map-based support for group decision making.