Bed load fluxes are typically calculated as a function of the reach averaged boundary shear stress and a representative bed grain size distribution. In steep, rough channels, heterogeneous bed surface texture and macro-roughness elements cause significant local deviations from the mean shear stress but this variability is often omitted in bed load calculations. Here we present a probabilistic bed load transport formulation that explicitly includes local variations in the flow field and grain size distribution. The model is then tested in a 10% gradient stream, to evaluate its predictive capability and to explore relations between surface grain size sorting and boundary shear stress. The boundary shear stress field, calculated using a quasi-3D hydraulic model, displayed substantial variability between patch classes, but the patch mean dimensionless shear stress varied inversely with patch median grain size. We developed an empirical relation between the applied shear stress on each patch class and the reach averaged shear stress and median grain size. Predicted sediment volumes using this relation in our bed load equation were as accurate as those using complete shear stress distributions and more accurate than current bed load transport equations. Our results suggest that when spatially variable grain size distributions (e.g., patches of sediment) are present they must be explicitly included in bed load transport calculations. Spatial variability in shear stress was relatively more important than grain size variations for sediment transport predictions.