A new algorithm is introduced for upscaling relative permeabilities, and tested in simulations of two-dimensional reservoir displacement processes. The algorithm is similar to existing algorithms for computing upscaled relative permeabilities from subgrid simulations, but uses new boundary conditions for the pressure field. The new 'effective flux boundary conditions' were introduced in a previous paper and provide a more accurate estimate of flux through high permeability channels. The algorithm was tested in conjunction with uniform grid coarsening and upscaled absolute permeabilities for a broad range of coarsenings. The permeability fields were highly heteroge-neous and layered, and were obtained from synthetic data and from conditioned realizations of actual oil reservoirs. The algorithm was tested for a wide variety of grid aspect ratios, and for both viscous-and gravity-dominated flow. Typical fine grids were of the order of 100x100 cells; the coarsest scaled-up grids were on the order of 5x5 cells. The quality of scale up was evaluated by comparing oil cut curves for the fine and coarse grid simulations. We consistently obtained excellent agreement, even at the coarsest levels of scale up.