Maintenance tasks and their application in the shipping industry have evolved significantly in the recent years. Particularly in the offshore industry, safety onboard, environmental protection and intensive operational activities necessitate the minimization of down-time and the preservation of an excellent performance ratio. The first step of an innovative ship maintenance strategy, which is proposed by the authors and is based on criticality and reliability assessment, is presented herein using the FTA tool with time-dependant dynamic gates so as to represent in an accurate and comprehensive way the interrelation of the components of a system. The paper also presents a review of the maintenance standards and procedures, such as the ALARP concept, the Key Programme 3-Asset Integrity (KP3) initiative, the OREDA handbook as well as the RCM and RBI principles. As part of the reliability assessment, the Birnbaum and Criticality reliability importance measures are utilized to validate the results of the analysis. A case study of a diving support vessel (DSV) illustrates the application of this strategy. The main systems examined are: the vessel's power plant, propulsion, water system, lifting, hauling and anchoring, diving and finally the safety system. The reliability of the main systems and subsystems as well as of their critical components is identified and suggestions of how to improve the overall reliability of the various systems both at a component, system and managerial level are also proposed.