Assessing soil organic carbon (SOC) stocks at a national scale provides relevant information on soil fertility and soil functions, such as soil water retention capacity, nutrient availability, and soil structure. Our overall goal is to map the SOC stock at the topsoil layer (0–30 cm) in Paraguay, using spatial information of key environmental factors (Environmental Factors - EF; 119 variables) related to SOC and by performing a Regression Kriging (RK) model. We fitted a RK model with 954 sample points, evaluating and computing the model uncertainty of SOC predictions with 10% of independent sample points. Our results show that on average, the SOC stock across Paraguay was 4,46 ± 2,66 kg m−2 where the highest SOC is found in humid regions covered by broad-leaf forests (8.66 × 10−6); while the lowest SOC is found within water-limited ecosystems (1.97 × 10−6). We determined that soil type, climate, and vegetation land cover were the strongest SOC predictors. Since this study represents the first Paraguayan effort to develop a SOC monitoring framework, it also provides the first national SOC map with its associated uncertainty. Enabling a unique opportunity to fulfill relevant information gaps and the extended opportunity to be used to validate global and regional SOC products.