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 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 standardised methods for sampling programs to quantify soil C stocks at national scales.