The shipping industry was responsible for about 3% of global greenhouse gas (GHG) emissions in 2018. In this context, the International Maritime Organisation (IMO) has established stringent targets to reduce GHG emissions by at least 50% by 2050 compared to 2008 levels. Replacing Heavy Fuel Oil (HFO) with Liquified Natural Gas (LNG) in Internal Combustion Engines (ICEs) is only one step in what should be a coordinated approach that combines both alternative fuels and more efficient technologies. This study evaluates the techno-economic feasibility of different hybridisation scenarios of ICE, Solid Oxide Fuel Cell (SOFC), and batteries to cover the energy demands of a large cruise ship. The SOFC modules are designed for five different fuels, including LNG, methanol, diesel, ammonia, and hydrogen. A multi-period optimization problem based on mixed integer linear programming is formulated to determine the optimal configuration and operational strategy of the system. The hybrid genset is designed to supply all heat and power needs of the ship, including both propulsion and hotel loads. The proposed hybridisation scenarios are evaluated representing the gradual replacement of ICEs for SOFCs and batteries, namely (i) ICE only (baseline configuration); (ii) ICE-SOFC-battery hybrid genset; and (iii) SOFC-battery hybrid genset. Methanol and diesel present the most promising results, despite high payback periods of 11 years, compared to the other fuels. Battery deployment was limited given limitations in the model and high investment costs.