Soil organic carbon (SOC) is a key soil property and particularly important for ecosystem functioning and the sustainable management of agricultural systems. Conventional laboratory analyses for the determination of SOC are expensive and slow. Laboratory spectroscopy in combination with chemometrics is claimed to be a rapid, cost-effective and non-destructive method for measuring SOC. The present study was carried out in Limpopo National Park (LNP) in Mozambique, a data- and access-limited area, with no previous soil spectral library. The question was whether a useful calibration model could be built with a limited number of samples. Across the major landscape units of the LNP, 129 composite topsoil samples were collected and analyzed for SOC, pH and particle sizes of the fine earth fraction. Samples were also scanned in a near-infrared (NIR) spectrometer. Partial least square regression (PLSR) was used on 1037 bands in the wavelength range 1.25–2.5 μm to relate the spectra and SOC concentration. Several models were built and compared by cross-validation. The best model was on a filtered first derivative of the multiplicative scatter corrected (MSC) spectra. It explained 83% of SOC variation and had a root mean square error of prediction (RMSEP) of 0.32% SOC, about 2.5 times the laboratory RMSE from duplicate samples (0.13% SOC). This uncertainty is a substantial proportion of the typical SOC concentrations in LNP landscapes (0.45–2.00%). The model was slightly improved (RMSEP 0.28% SOC) by adding clay percentage as a co-variable. All models had poorer performance at SOC concentrations above 2.0%, indicating a saturation effect. Despite the limitations of sample size and no pre-existing library, a locally-useful, although somewhat imprecise, calibration model could be built. This model is suitable for estimating SOC in further mapping exercises in the LNP.