Carbon (C) present in lake sediments is an important global sink for CO2; however, an in-depth understanding of the impact of climate variability and the associated changes in vegetation on sediment C dynamics is still lacking. A total of 13 lakes were studied to quantify the influence of climate and vegetation on the reconstructed Holocene C accumulation rate (CAR) in lake sediments of the modern East Asian monsoonal margin. The corresponding paleoclimate information was assessed, including the temperature (30–90°N in the Northern Hemisphere) and precipitation (indicated by the δ18O of the Sanbao, Dongge, and Hulu caves). The Holocene vegetation conditions were inferred by pollen records, including arboreal pollen/non-arboreal pollen and pollen percentages. The results showed that the peak CAR occurred during the mid-Holocene, coinciding with the strongest period of the East Asian summer monsoon and expansion of forests. Lakes in the temperate steppe (TS) regions had a mean CAR of 13.41 ± 0.88 g C m−2 yr−1, which was significantly greater than the CARs of temperate desert (TD) and highland meadow/steppe (HMS; 6.76 ± 0.29 and 7.39 ± 0.73 g C m−2 yr−1, respectively). The major influencing factor for the TS sub-region was vegetation dynamics, especially the proportion of arboreal vegetation, while temperature and vegetation coverage were more important for the HMS. These findings indicate that C accumulation in lake sediments is linked with climate and vegetation changes over long timescales; however, there was notable spatial heterogeneity in the CARs, such as opposing temporal changes and different major influencing factors among the three sub-regions during the mid-Holocene. Aridification and forest loss would decrease C storage. However, prediction of C accumulation remains difficult because of the spatial heterogeneity in CARs and the interaction between the CAR and various factors under future climate change conditions.