Accurately identifying clouds in imagery is a key preprocessing step in satellite remote sensing applications. In order to address problems of cloud samples required for cloud detection, such as reliance on manual interpretation, high collection costs, and limited quantity, this paper proposed a universal and automatic construction algorithm for cloud sample database (UAC-CSD) to create a large database of accurate and representative global cloud samples. The UAC-CSD sample database was applied and validated against Landsat 8 biome (L8_Biome) and spatial procedures for automated removal of cloud and shadow (SPARCS) datasets. The overall accuracies of random forest (RF) based on UAC-CSD sample database for cloud masking reached 0.921 on L8_Biome and 0.900 on SPARCS, which showed higher accuracies than RF based on Fmask4.0 sample database (0.869 and 0.866). Moreover, the UAC-CSD sample database was freely shared and could support the training and verification of various machine learning models. In addition to RF, light gradient boosting machine (LightGBM), multilayer perceptron (MLP), and support vector machine (SVM) were also trained based on UAC-CSD sample database and verified using L8_Biome. The results showed that the overall accuracies of models trained on UAC-CSD sample database were basically higher than models trained on Fmask4.0, and computational efficiencies were also greatly improved. This study provides global cloud samples with different cloud characteristics and covering different land covers for cloud detection models, which increases generalization ability of models and improves the accuracy and efficiency of processing massive medium to fine resolution satellite data in the big data era.