Although the greening of the marine sector started over a decade ago, the emissions produced from ships and port operating equipment have been only recently perceived as issues to be addressed. On this basis, the International Maritime Organisation (IMO) decided to enact stricter sulphur limits on the fuel oil used by ships in Sulphur Oxide (SOx) Emission Control Areas in an effort to reduce the environmental impact of the vessel’s bunkers. In this respect, the purpose of the paper is to quantify the cost implications of the IMO revised regulations on the shippers’ traditional supply chain network design decisions through the development of a strategic Mixed Integer Linear Programming decision-support model. The applicability of the model is demonstrated on a realistic maritime supply chain operating within the East Asia—EU trade route. The results reveal that the implementation of the sulphur limits at the route’s ports may not affect the shippers’ network structure under the current fuel prices, as the optimally selected ports have cost effective hinterland transportation connections within the EU market, that make them preferable for the shipper, even though the network’s shipping costs increase.