We have studied the impact of heterogeneity on relative permeability and residual trapping for rock samples from the Bunter sandstone of the UK Southern North Sea, the Ormskirk sandstone of the East Irish Sea, and the Captain sandstone of the UK Northern North Sea. Reservoir condition CO2-brine relative permeability measurements were made while systematically varying the ratio of viscous to capillary flow potential, across a range of flow rates, fractional flow, and during drainage and imbibition displacement. This variation resulted in observations obtained across a range of core-scale capillary number math formula. Capillary pressure heterogeneity was quantitatively inferred from 3-D observations of the fluid saturation distribution in the rocks. For each of the rock samples, a threshold capillary number, math formula, was found, below which centimeter-scale layering resulted in a heterogeneous distribution of the fluid phases and a commensurate impact on flow and trapping. The threshold was found to be dependent on the capillary number alone, irrespective of the displacement path (drainage or imbibition) and average fluid saturation in the rock. The impact of the heterogeneity on the relative permeability varied depending on the characteristics of the heterogeneity in the rock sample, whereas heterogeneity increased residual trapping in all samples above what would be expected from the pore-scale capillary trapping mechanism alone. Models of subsurface CO2 injection should use properties that incorporate the impacts of heterogeneity at the flow regime of interest or risk significant errors in estimates of fluid flow and trapping.