Gas emissions are a major source of the air pollution that causes global warming, climate changes and ozone layer depletion. A large portion of these pollutants come from crude oil refining in the form of nitrogen oxides (NOx), sulfur oxides (SOx) and volatile organic compounds (VOC). Gas emissions can be mitigated during crude oil refining using different methods associated with different investment costs. The aim of this paper is to develop an optimization model that identifies the best mitigation technology with minimum cost. A case study is presented for a refinery in Saudi Arabia that has three mitigation alternatives for gas emissions reduction, namely, balancing, fuel switching and specialized technologies. The effect on the plant’s profitability is studied with different reduction targets (20% to 90% cut in emissions). The profit margin of the refinery for each scenario is formulated as a mixed integer nonlinear programming model. The model enables the plant’s management to correlate emission reduction to its effect on the refinery’s profitability. The results of the model urge the revision of legislation to offer incentive packages for plants that achieve higher pollutant reduction. Also, a universal curve is obtained for the fractional loss of profitability as a function of percent reduction of specific pollutant emissions. This is achieved by relating the loss in profitability to that of an equivalent “zero-emissions” refinery.