Shrub encroachment has significant impacts on carbon (C) and nitrogen (N) dynamics of grassland ecosystems, but, how it influences soil organic C (SOC) and soil total N (STN) stocks of grasslands is not well documented, especially in deep soils. Here, we examined these effects by investigating the SOC density (SOCD) and the STN density (STND) at depths of up to 5 m in shrub patches and grassy matrix at 18 grassland sites in Inner Mongolia, China. Our results revealed that 44.0–54.1% of SOC and 65.5–74.8% of STN were stored in soil layers of 100 cm to 500 cm, and that shrub encroachment resulted in a significant accumulation of SOC and STN in shrub patches. The mean SOCD at 0–500 cm soil layers in shrub patches and grassy matrix was 11.34 and 8.39 kg C m^-2, respectively, and the mean STND was 2.45 and 2.13 kg N m^-2, respectively. These differences between the shrub patches and grassy matrix were equivalent to an increase in the mean SOC and STN stocks of 2.95 kg C m^-2 and 0.32 kg N m^-2, respectively. Increases in SOCD and STND mainly occurred in 30–300 cm soil layers, and varied between typical grassland and desert grassland. The changes in SOCD and STND exhibited significant negative correlations with temperature and pH and positive correlations with precipitation and plant biomass. Our findings suggest that shrub encroachment can significantly accumulate SOC and STN in deep soils in temperate grasslands, which helps to understand soil C and N dynamics in shrub-encroached grasslands.