Shrub species are expanding across the Arctic in response to climate change and biotic interactions. Changes in belowground carbon (C) and nitrogen (N) storage are of global importance because Arctic soils store approximately half of global soil C. We collected 10 (60 cm) soil cores each from graminoid- and shrub-dominated soils in western Greenland and determined soil texture, pH, C and N pools, and C:N ratios by depth for the mineral soil. To investigate the relative chemical stability of soil C between vegetation types, we employed a novel sequential extraction method for measuring organo-mineral C pools of increasing bond strength. We found that (i) mineral soil C and N storage was significantly greater under graminoids than shrubs (29.0 ± 1.8 versus 22.5 ± 3.0 kg·C·m−2 and 1.9 ± .12 versus 1.4 ± 1.9 kg·N·m−2), (ii) chemical mechanisms of C storage in the organo-mineral soil fraction did not differ between graminoid and shrub soils, and (iii) weak adsorption to mineral surfaces accounted for 40%–60% of C storage in organo-mineral fractions — a pool that is relatively sensitive to environmental disturbance. Differences in these C pools suggest that rates of C accumulation and retention differ by vegetation type, which could have implications for predicting future soil C pool storage.