Aerosols from biomass burning can alter the radiative balance of the Earth by reflecting and absorbing solar radiation1 . Whether aerosols exert a net cooling or a net warming effect will depend on the aerosol type and the albedo of the underlying surface2 . Here, we use a satellite-based approach to quantify the direct, top-of-atmosphere radiative effect of aerosol layers advected over the partly cloudy boundary layer of the southeastern Atlantic Ocean during July–October of 2006 and 2007. We show that the warming effect of aerosols increases with underlying cloud coverage. This relationship is nearly linear, making it possible to define a critical cloud fraction at which the aerosols switch from exerting a net cooling to a net warming effect. For this region and time period, the critical cloud fraction is about 0.4, and is strongly sensitive to the amount of solar radiation the aerosols absorb and the albedo of the underlying clouds. We estimate that the regional-mean warming effect of aerosols is three times higher when large-scale spatial covariation between cloud cover and aerosols is taken into account. These results demonstrate the importance of cloud prediction for the accurate quantification of aerosol direct effects.