Monitoring the spatial and temporal changes in soil organic carbon (SOC) brought about by climate change and agricultural practices is challenging because existing SOC monitoring methods are very time and resource consuming. This study examined the use of visible near-infrared spectroscopy (Vis-NIR) as a speedy method to predict SOC and to monitor spatial and temporal changes in SOC compared with labor-intensive traditional laboratory (TL) measurements. For SOC prediction, topsoil (0–25 cm) and subsoil (25–50 cm) samples in the Danish soil spectral library for the years 1986 and 2009 were used. Empirical Bayesian Kriging was used to map SOC. The Vis-NIR predictions indicated that average topsoil and subsoil SOC had decreased slightly in Denmark from 1986 to 2009, and this was confirmed by TL measurements of SOC. In East Denmark, Vis-NIR predictions differed significantly from the measured SOC values. For subsoil samples, the ability of Vis-NIR to predict SOC levels varied. In West Jutland, Central Jutland, North Jutland, and Thy, Vis-NIR–predicted SOC levels did not differ from TL-measured levels, showing good predictive ability. For topsoil samples, the spatial pattern of change in TL-measured and predicted SOC was consistent during the 23-year study period, but there were significant discrepancies in the corresponding SOC change patterns for subsoil samples. To conclude, Vis-NIR is a promising method for monitoring spatial and temporal changes in SOC at the national scale, especially in the topsoil. Some difficulties can arise in low SOC subsoils, so more systematic work is needed to improve the method for practical applications.