When sailing on the open seas, far from onshore dockyards, if a crucial part of the ship’s machinery fails, the ship will experience a costly event that carries a high risk of seriously affecting ship operations. If the ship receives warning of an impending defect, then it can try to sail to a dockyard and simultaneously order the spare parts needed to fix the problem. In this paper, we define this type of maintenance situation as ‘vessel emergency maintenance’. It is a complex problem, due to uncertainties with both the machinery condition development and spare parts delivery. To solve this problem, our paper proposes a bi-objective model under a condition-based maintenance strategy, with the aim of simultaneously minimizing maintenance costs and maximizing ship reliability. Maintenance costs include four things: (1) fuel consumption costs; (2) renting extra vessels; (3) shipping delay penalty costs; and (4) spare parts inventory costs. Ship reliability is represented by the reliability of the ship’s main engine, and can be described through a stochastic process. To solve this bi-objective model, we employ a non-dominated sorting genetic algorithm II (NSGA-II) to generate the Pareto optimal front of the two objectives. A numerical experiment is presented to demonstrate the applicability of the proposed model. The results indicate that the proposed model can provide emergency maintenance decision support for ship operators while they are sailing at sea.