This paper addresses the fleet renewal problem and particularly the treatment of uncertainty in the maritime case. A stochastic programming model for the maritime fleet renewal problem is presented. The main contribution is that of assessing whether or not better decisions can be achieved by using stochastic programming rather than employing a deterministic model and using average data. Elements increasing the relevance of uncertainty are also investigated. Tests performed on the case of Wallenius Wilhelmsen Logistics, a major liner shipping company, show that solutions to the model we present perform noticeably better than solutions obtained using average values.