With rising concerns about emissions from shipping, fuel cells are expected to take an important role in ship propulsion. In particular, solid oxide fuel cells (SOFC) offer high efficiency with the possibility of combined heat and power production. In this paper, we investigate energy, cost, and emission savings on ships resulting from the use of SOFCs using an optimization-based approach. A global sensitivity analysis was used to investigate the effects of the high uncertainty of problem parameters. This setup is applied to two case studies: a cruise ship and a tanker. The results show that SOFCs could provide a reduction in ship greenhouse gas emissions by up to 34% and that when using natural gas as fuel, SOFCs are the most cost-optimal solution that allows a significant reduction in GHG emissions. A wider adoption of SOFCs would also lead to a decrease of other pollutant emissions. The sensitivity analysis shows that the lifetime of the stack is the most impacting uncertain parameter, followed by fuel prices and by the investment cost of the SOFC stack. The study highlights that, in a future of stricter constraints on greenhouse gas emissions and where the SOFC technology will be fully industrialized, SOFCs will be able to play an important role in bridging shipping towards decarbonization.