Marine remote sensing provides comprehensive characterizations of the ocean surface across space and time. However, cloud cover is a significant challenge in marine satellite monitoring. Researchers have proposed various algorithms to fill data gaps “below the clouds”, but a comparison of algorithm performance across several geographic regions has not yet been conducted. We compared ten basic algorithms, including data-interpolating empirical orthogonal functions (DINEOF), geostatistical interpolation, and supervised learning methods, in two gap-filling tasks: the reconstruction of chlorophyll a in pixels covered by clouds, and the correction of regional mean chlorophyll a concentrations. For this purpose, we combined tens of cloud-free images with hundreds of cloud masks in four study areas, creating thousands of situations in which to test the algorithms. The best algorithm depended on the study area and task, and differences between the best algorithms were small. Ordinary Kriging, spatiotemporal Kriging, and DINEOF worked well across study areas and tasks. Random forests reconstructed individual pixels most accurately. We also found that high levels of cloud cover led to considerable errors in estimated regional mean chlorophyll a concentration. These errors could, however, be reduced by about 50% to 80% (depending on the study area) with prior cloud-filling.