A robust and reliable chlorophyll-a (Chla) concentration algorithm is still lacking for optically complex waters due to the lack of understanding of the bio-optical process. Machine learning approaches, which excel at detecting potential complex nonlinear relationships, provide opportunities to estimate Chla accurately for optically complex waters. However, the uncertainties in atmospheric correction (AC) may be amplified in different Chla algorithms. Here, we aim to select one state-of-the-art algorithm or establish a new algorithm based on machine learning approaches that less sensitive to AC uncertainties. Firstly, nine state-of-the-art empirical, semianalytical, and optical water types (OWT) classification-based Chla algorithms were implemented. These existing algorithms showed good performance by using in situ database, however, failed in actual OLCI applications due to their sensitivity to AC uncertainties. Thus, four popular machine learning approaches (random forest regression (RFR), extreme gradient boosting (XGBoost), deep neural network (DNN), and support vector regression (SVR)) were then employed. Among them, the “RFR-Chla” model performed the best and showed less sensitivity to AC uncertainties. Finally, the Chla spatiotemporal variations in 163 major lakes across eastern China were mapped from OLCI between May 2016 and April 2020 using the proposed RFR-Chla model. Generally, the lakes in eastern China are severely eutrophic, with an average Chla concentration of 33.39 ± 6.95 μg/L. Spatially, Chla in the south of eastern China was significantly higher than those in northern lakes. Seasonally, Chla was high in the summer and autumn and low in the spring and winter. This study provides a reference for water quality monitoring in turbid inland waters suffering certain AC uncertainties and supports aquatic management and SDG 6 reporting.