Compared with the humid region in southern China, the sandy land vegetation is characterized by low coverage and a scattered spatial distribution in the north. Shrub is a dominant vegetation type in this region and plays an important role in sand control, food/timber product provision, etc. In view of the current lack of the medium- and high-resolution remote sensing products for shrub coverage at large-scale in arid regions, we proposed a new approach to estimate shrub coverage at large scale based on Collect Earth sample collector and Google Earth Engine (GEE) platform. Then this approach was applied to Mu Us sandy land, one of the four major sandy lands in Northern China. The results showed that:(1) Collect Earth sample collector could effectively obtain the ground shrub coverage sample data set for distinguishing shrubs from tall trees and herbaceous vegetation, which laid a foundation for the establishment of shrub coverage estimation; (2) Using Landsat data, other ancillary data, and the machine learning algorithm in GEE, the shrub coverage could be estimated effectively. The CART model had a deterministic coefficient R² of 0.73 and a Root Mean Square Error (RMSE) of 13.66% with the estimated Accuracy (EA) of 61.8%. For SVM model, R², RMSE, and EA were 0.72, 13.73%, and 61.6%, respectively. (3) The GEE-based approach proposed in this study could provide support to shrub coverage estimation in sandy land at the national and even the global scale with a potential application.