Cloud detection is one of the key components for the exploitation of Earth observation images. We discuss the use of probabilistic algorithms for MERIS and AATSR on-board the ENVISAT satellite. As a new approach, we used an automated search to find the best combination of channels for the algorithm, which led to a number of unusual combinations that have not been used in the past. We show how very small samples of manually classified cloud truth images can be used to set up efficient algorithms.