The potential carbon sequestration in rangelands is largely due to the extensive areas they occupy, even though levels of soil organic carbon (SOC) are low. There is considerable uncertainty in achieving this potential due to the inherent patchy spatial and temporal distribution of rangeland vegetation and resources. At a paddock scale, determining appropriate sampling scales is a critical first step in the accurate estimation of size and spatial distribution of stocks of SOC. This issue was addressed by examining the spatial distribution of SOC and determining the association of SOC with other site characteristics such as ground cover and vegetation. This was done in a pilot study conducted in a 136-ha paddock located on the Cobar Pediplain Bioregion in western New South Wales, Australia. Each of 104 sites was sampled using a 0.25-m2 quadrat to assess biomass and ground cover category (percentage of perennial plants, bare ground, cryptogams, annual plants and litter) of a soil core taken from the centre of each quadrat, and proximity to trees and shrubs. The soil core was used to determine total organic C (TOC), total N (TN) and the C:N ratio at four depths (0-5; 5-10; 10-20; 20-30cm). From the quadrat and ground cover categories of the soil cores, six microsite categories were identified using cluster analysis: cryptogams; litter (≥25% litter); bare (≥60% bare ground); annual (≥40% annual plants); litter-P (≥15% litter and ≥10% perennial plants) and perennial (≥30% perennial plants). Microsite, depth in soil profile and the presence of trees and shrubs all had a significant (P<0.001) effect on TOC concentration. The predicted means (s.e. of mean) of TOC at the soil surface (0-5cm) were perennial 1.26 (0.04) %; litter-P 1.20 (0.05) %; annual 1.18 (0.06) %; litter 1.12 (0.05) %; bare 1.03 (0.05) % and cryptogams 0.88 (0.06) %. Higher concentrations of TOC were associated with the presence of trees and were almost 30% higher in close proximity (<1m) to a tree. There was a consistent finding that higher concentrations of TOC, TN and the high values of C:N ratio were each associated with higher ground cover of perennial plants. The autocorrelation range for soil C stocks was ∼30m and for categories of ground cover which varied from 10m to over 200m. The spatial predictions for ground cover of perennial plants closely mirrored those for C stocks, which were 22.9MgCha-1 in the top 30cm of soil in this environment. As both tree proximity and ground cover had a significant effect on TOC, quantifying the levels of soil organic C at a paddock scale will require an understanding of the spatial patterns of vegetation (woody and ground cover), which provides a basis for within-paddock stratification before soil sampling.