Dryland soils have the potential to be large atmospheric carbon (C) sinks, thus aiding in managing global warming. In these areas, soil micro-organisms found in biological soil crusts (biocrusts) can play a major role in C cycling, especially by influencing the fluxes between the atmosphere and soil; however, their potential has been reduced due to degradation. Thus, we assessed how inoculating soil micro-organisms and adding microbial stimulant nutrients onto a degraded soil affected C sequestration. Therefore, a full factorial combination of bacteria, cyanobacteria and nutrients was added to the field-collected soil. After 60 days, we measured the effect of this inoculation with and without support by a nutrient (B4) addition on the soil organic C; then, we calculated the C sequestration and the potential CO2 removal from the atmosphere. We found that inoculating bacteria, cyanobacteria, or a combination of them increased the sequestrated C in the soil from 0.232 to 0.294 gm−2 day−1 at the plot scale; when calculations were used to scale up, this increase was from 0.84 to 1.07 ton ha−1 year−1. This could remove 3.11–3.93 ton ha−1 year−1 of CO2 from the atmosphere. However, nutrient addition had no significant effect on the C pools.