The patterns of spatio-temporal variability of the soil organic carbon (SOC) stored in karst catchment were investigated, to provide a scientific basis for estimating SOC storage in karst regions and selecting technical measures for soil carbon sequestration. In this paper, field sampling, laboratory measurement, geostatistics, and geographic information system (GIS) were combined, to investigate the patterns and influencing factors of SOC’s spatio-temporal variability in Houzhai catchment from 1980 to 2015. The results showed that according to the soil samples of the entire catchment, the SOC content averaged 21.98 g/kg in 1980 and 25.07 g/kg in 2015, with an increase of 3.09 g.kg–1 (14.58%). Over the three and a half decades, SOC in this region showed weakened spatial structure, reduced correlation, and broken spatial distribution. Moreover, SOC in both periods presented a pattern of high values in the east and low values in the west, high in the periphery and low in the centre, and high in the south and low in the north. However, some local values were highly variable in embedded or block distribution. The key factors that could affect spatio-temporal variability of SOC in Houzhai catchment included the soil types, land utilisation, and major environmental factors.