The maritime industry faces the urgent challenge of reducing greenhouse gas (GHG) emissions while maintaining economic viability, especially under the International Maritime Organization’s (IMO) Net-Zero Framework and Carbon Intensity Indicator (CII). Optimizing ship speed is a key operational measure, but it involves a complex trade-off between fuel consumption, voyage time, and regulatory compliance costs. This paper presents a multi-objective ship speed optimization method using Evolutionary Deep Learning (EDL). In this study, EDL is defined as the integration of a deep gradient boosting fuel predictor (CatBoost) and a gradient-free evolutionary optimizer (Natural Evolution Strategies, NES). A hybrid fuel consumption prediction model combines ISO 15016:2015 physical constraints with CatBoost, achieving a Mean Absolute Percentage Error of 6.45%. The optimization model minimizes total operating costs and GHG emissions, incorporating Greenhouse Gas Fuel Intensity (GFI) compliance costs, CII rating constraints, and a voyage segmentation strategy. The problem is solved with an NES algorithm using Gaussian population representation and an elitism strategy. A case study of a transpacific voyage of a large container vessel (COSCO PACIFIC) shows that the proposed EDL method achieves the lowest GHG emissions among all benchmark algorithms (reducing CO₂eq by 9.18% compared to NSGA-II) and the fastest computation time (63.9% shorter than NSGA-II). While MOPSO and MOACO yield lower raw fuel costs by sacrificing emissions and compliance performance, EDL attains a superior balance across all objectives—emissions, compliance costs, and Comprehensive Fitness—with robust convergence and high computational efficiency. This approach offers practical support for sustainable ship navigation under complex regulatory pressures.