The accurate measurement of the soil organic carbon (SOC) stock in Australian grazing lands is important due to the major role that SOC plays in soil productivity and the potential influence of soil C cycling on Australia's greenhouse gas emissions. However, the current sampling methodologies for SOC stock are varied and potentially conflicting. It was the objective of this paper to review the nature of, and reasons for, SOC variability; the sampling methodologies commonly used; and to identify knowledge gaps for SOC measurement in grazing lands. Soil C consists of a range of biological materials, in various SOC pools such as dissolved organic C, micro- and meso-fauna (microbial biomass), fungal hyphae and fresh plant residues in or on the soil (particulate organic C, light-fraction C), the products of decomposition (humus, slow pool C) and complexed organic C, and char and phytoliths (inert, passive or resistant C); and soil inorganic C (carbonates and bicarbonates). Microbial biomass and particulate or light-fraction organic C are most sensitive to management or land-use change; resistant organic C and soil carbonates are least sensitive. The SOC present at any location is influenced by a series of complex interactions between plant growth, climate, soil type or parent material, topography and site management. Because of this, SOC stock and SOC pools are highly variable on both spatial and temporal scales. This creates a challenge for efficient sampling. Sampling methods are predominantly based on design-based (classical) statistical techniques, crucial to which is a randomised sampling pattern that negates bias. Alternatively a model-based (geostatistical) analysis can be used, which does not require randomisation. Each approach is equally valid to characterise SOC in the rangelands. However, given that SOC reporting in the rangelands will almost certainly rely on average values for some aggregated scale (such as a paddock or property), we contend that the design-based approach might be preferred. We also challenge soil surveyors and their sponsors to realise that: (i) paired sites are the most efficient way of detecting a temporal change in SOC stock, but destructive sampling and cumulative measurement errors decrease our ability to detect change; (ii) due to (i), an efficient sampling scheme to estimate baseline status is not likely to be an efficient sampling scheme to estimate temporal change; (iii) samples should be collected as widely as possible within the area of interest; (iv) replicate of laboratory analyses is a critical step in being able to characterise temporal change. Sampling requirements for SOC stock in Australian grazing lands are yet to be explicitly quantified and an examination of a range of these ecosystems is required in order to assess the sampling densities and techniques necessary to detect specified changes in SOC stock and SOC pools. An examination of techniques that can help reduce sampling requirements (such as measurement of the SOC fractions that are most sensitive to management changes and/or measurement at specific times of the year, preferably before rapid plant growth, to decrease temporal variability), and new technologies for in situ SOC measurement is also required.