Maintenance scheduling for naval vessels and ships requires ongoing improvement to manage rising maintenance costs within availability constraints. Existing maintenance scheduling approaches are not optimal as maintenance costs continue to rise without an improvement in vessel availability. This paper reviews the Risk-Based Maintenance Scheduling (RBM) framework as applied to ships and naval vessels, and provides a critical analysis of Risk Assessment and Maintenance Scheduling techniques used. Further, objectives and considerations are defined for future applications for ships and naval vessels, and the framework evaluated as an improvement on existing Preventative Maintenance (PM) and Reliability Centered Maintenance (RCM) methods. A probabilistic approach supported by condition monitoring data in combination with Decision Theory is suggested for the Risk Assessment and Maintenance Scheduling elements comprising an RBM Scheduling framework. Implementation of this framework from both periodic PM and RCM is presented. Development of applications from the component level upwards is suggested. Availability and overall maintenance cost are suggested as evaluation metrics against existing methods. The development of an application is formalized within a proposed framework. The development of an application within the RBM Scheduling framework is expected to result in reduced maintenance costs while meeting availability requirements for ship and naval vessel applications.