Shrub encroachment frequently occurs in arid and semi-arid grasslands worldwide and affects the regional carbon balance. Many previous studies have revealed the effects of shrub encroachment on bulk carbon content of grasslands, but molecular evidence is surprisingly lacking. In this study, we examined the chemical composition of plant tissues and soil organic carbon (SOC), and soil microbial communities to identify the effects of shrub (Caragana microphylla) encroachment on SOC storage in the top layer (0–10 cm) along a gradient of natural shrub cover in the grasslands of Inner Mongolia. We found that SOC in the shrub patches was derived mainly from leaves, whereas SOC in the grassy matrix was composed of a mixture of fresh root- and leaf-derived compounds. Compared with pure grassland, the SOC decreased by 29% in the shrub-encroached grasslands (SEGs), and this decrease was enhanced by increasing shrub cover. We also found that free lipids and lignin-derived phenols increased while the ratios of ω-C₁₈/∑C₁₈ and suberin/cutin decreased with increasing shrub cover. In addition, the ratios of fungal to bacterial phospholipid fatty acids (PLFAs) and gram-negative to gram-positive bacterial PLFAs decreased with increasing shrub cover. These results indicate that the encroachment of nitrogen-rich legume shrubs can lead to carbon loss by altering the chemical composition of plant inputs as well as the soil microbial community in grassland ecosystems.