Carbon Capture and Storage (CCS) is the process of capturing CO2 before it enters the atmosphere, transporting it, and then storing the CO2 in a permanent underground storage site. CCS is projected to play an important role for compliance with the temperature degree goals set by the Paris Agreement, and with this in mind, we study the so-called Ship-Based CCS Logistics Problem (SCLP). The SCLP deals with designing a cost-effective ship-based logistics system to ensure that CO2 captured from emission sources in the hinterland of loading ports is transported to unloading ports nearby the final storage sites. As part of this, one needs to determine the intermediate storage capacities at the loading ports, ship fleet size and mix, fleet deployment and sailing speeds along each chosen route. To solve the SCLP, we propose a new mixed integer programming model, where candidate ship routes are generated as input. We use our optimization model to analyze three future supply scenarios based on estimations of the volume of captured CO2 from emission sources in mainland Europe that is brought via ports of Antwerp, Dunkirk, Rotterdam and Wilhelmshaven to Norwegian storage sites. Our computational results show that the logistics cost per tonne of CO2 will be around 10 Euros in low volume scenarios and drop to about 8 Euros in high demand scenarios due to economies of scale. In the considered high demand scenario for the year 2050 about 100 ships are required that perform several thousand round trips per year within the considered port network.