This article presents a new holistic multi-objective design approach for the optimization of Arctic Offshore Supply Vessels (OSVs) for cost- and eco-efficiency. The approach is intended to be used in the conceptual design phase of an Arctic OSV. It includes (a) a parametric design model of an Arctic OSV, (b) performance assessment models for independently operating and icebreaker-assisted Arctic OSVs, and (c) a novel adaptation of the Artificial Bee Colony (ABC) algorithm for multi-objective optimization of Arctic OSVs. To demonstrate the feasibility and viability of the proposed optimization approach, a series of case studies covering a wide range of operating scenarios are carried out. The results of the case studies indicate that the consideration of icebreaker assistance significantly extends the feasible design space of Arctic OSVs, enabling solutions with improved energy- and cost-efficiency. The results further indicate that the optimal amount of icebreaking assistance and optimal vessel speed differs for different vessels, highlighting the motivation for holistic design optimization. The applied adaptation of the ABC algorithm proved to be well suited and efficient for the multi-objective optimization problem considered.