This paper addresses procurement planning in oil refining, which has until now only had limited attention in the literature. We introduce a mixed integer nonlinear programming (MINLP) model and develop a novel two-stage solution approach, which aims at computational efficiency while addressing the problems due to discrepancies between a non-linear and a linearized formulation. The proposed model covers realistic settings by allowing the blending of crude oil in storage tanks, by modeling storage tanks and relevant processing units individually, and by handling more crude oil types and quality parameters than in previous literature. The developed approach is tested using historical data from Statoil A/S as well as through a comprehensive numerical analysis. The approach generates a feasible procurement plan within acceptable computation time, is able to quickly adjust an existing plan to take advantage of individual procurement opportunities, and can be used within a rolling time horizon scheme. (C) 2013 Elsevier Ltd. All rights reserved.