The number of soil samples required to predict the minimum detectable change in soil carbon was estimated using a regression estimator and compared with the sampling demand based on classical statistical theory in the three large no-till production fields of Nebraska. Soil carbon stock (SOC) was measured at about 200 sampling locations per field in 0 to 0.3 m depth. Exhaustive auxiliary information (soil electrical conductivity and soil surface reflectance) was obtained for 4 m x 4 m grid cells at each site. A bootstrap procedure was used to obtain sample sizes ranging from 10 to 200 samples per site (100 replicates) and the minimum detectable difference (MDD) in SOC was calculated for each sample size. Using the classical statistical estimator of mean SOC, the sample size required to predict a MDD of 5 Mg C/ha ranged from 150 to more than 200 samples. Using a regression estimator that predicted SOC as a field-specific function of exhaustive auxiliary information, only 70 to 90 samples/site were required to achieve a MDD of 5 Mg C/ha. The regression estimator was about 50 to 60% more efficient than the classical sample mean. In a second bootstrap analysis, a common regression estimator was used for all three sites instead of field-specific regression models. The use of a common regression estimator resulted in only slightly higher sampling demand than the field-specific regression approach. The common regression estimator was 40 to 55% more efficient than the common classical sample mean. Our analysis demonstrates that readily available correlated auxiliary information is likely to significantly increase the precision of soil C stock estimates and allows monitoring of changes over time with about 50% less sampling cost.