For the past two decades, the need to shield strategic maritime interests, to tackle criminality and terrorism at or from the sea and to conserve valuable marine resources has been recognized at the highest political level. Acknowledging and accounting for the interplay between climate change, the vulnerability of coastal populations and the occurrence of maritime criminality should be part of any ocean governance process. Still, given the complex interactions between climate change and socio-economic components of the marine realm, it has become urgent to establish a solid methodological framework, which could lead to sound and effective decisions. We propose that any such framework should not be built from scratch. The adaptation of well tested, existing uncertainty-management tools, such as Cumulative Effect Assessments, could serve as a solid basis to account for the magnitude and directionality of the dependencies between the impacts of climate change and the occurrence of maritime criminality, offering spatial explicit risk evaluations. Multi-Criteria Decision Making could then be employed to better and faster inform decision-makers. These mechanisms could provide a framework for comparison of alternative mitigation and adaptation actions and are essential in assessing responses to tackle maritime crime in the context of climate change.