Researchers are increasingly studying carbon (C) storage by natural ecosystems for climate mitigation, including coastal ‘blue carbon’ ecosystems. Unfortunately, little guidance on how to achieve robust, cost-effective estimates of blue C stocks to inform inventories exists. We use existing data (492 cores) to develop recommendations on the sampling effort required to achieve robust estimates of blue C. Using a broad-scale, spatially explicit dataset from Victoria, Australia, we applied multiple spatial methods to provide guidelines for reducing variability in estimates of soil C stocks over large areas. With a separate dataset collected across Australia, we evaluated how many samples are needed to capture variability within soil cores and the best methods for extrapolating C to 1 m soil depth. We found that 40 core samples are optimal for capturing C variance across 1000's of kilometres but higher density sampling is required across finer scales (100–200 km). Accounting for environmental variation can further decrease required sampling. The within core analyses showed that nine samples within a core capture the majority of the variability and log-linear equations can accurately extrapolate C. These recommendations can help develop standardized methods for sampling programmes to quantify soil C stocks at national scales.