In this paper we investigate maintenance policy selection (MPS) through the use of the Analytic Hierarchy Process (AHP). A maintenance policy is a policy that dictates which parameter triggers a maintenance action. In practice, selecting the right maintenance policy appears to be a difficult decision. We investigate MPS for naval ships, but our results have wider applicability. For our study we cooperate with the owner and operator of the ships, as well as with a shipbuilder and an original equipment manufacturer of naval ships. We apply a structured five step approach to obtain the relevant criteria that may make one policy preferable over another. The criteria are drawn from both literature and a series of interviews at several navy related companies and are structured into a hierarchy of criteria usable with the AHP. Additionally, we organize three workshops at the three different companies to test the AHP-based MPS approach in practice. We conclude that the AHP is well suited for maintenance policy selection in this broad setting, and that it provides a structured and detailed approach for MPS. Adding to that, it facilitates discussions during and after the sessions, creating a better understanding of the policy selection process.