Shipping companies repeatedly face the problem of adjusting their vessel fleet to meet uncertain future transportation demands and compensating for aging vessels. In this paper, a new multi-stage stochastic programming formulation for strategic fleet renewal in shipping is proposed. The new formulation explicitly handles uncertainty in parameters such as future demand, freight rates and vessel prices. Extensive computational tests are performed, comparing different discretizations of the uncertain variables and different lengths of the planning horizon. It is shown that significantly better results are obtained when considering the uncertainty of future parameters, compared to using expected values.