In this paper we consider the reduction of air emissions from vessels when uncertainty is taken into account. Uncertainty in the reduction effects of the different existing air emission controls is currently high and makes their selection for vessel emission regulations compliance a challenging process. We develop a two-stage stochastic optimization model that addresses this uncertainty. The model’s objective is to plan the installation of air emission controls over a specified time horizon for a vessel to comply in the most cost-efficient way with the air emission regulations. The uncertain reduction effects of the controls are modelled by a set of scenarios. The approach is applied to a case study with real data. The solution exposes the important impact of uncertainty on this problem, especially on the SO X reduction, while the CO2 reduction plan seems in this case not affected by uncertainty.