A series of regional pilot geochemical survey projects have been carried out in Australia over recent years. These pilot projects targeted a number of landscape and climate settings that are challenging for geochemical mapping, and applied increasingly lower sampling densities, from c. 1 site/300 km2 to c. 1 site/ 2100 km2. Selected results are presented from pilot geochemical surveys in the Riverina, Gawler and Thomson regions, as well as results from modelling aimed at testing the robustness of ultra-low sampling densities in Australia. The salient conclusions are that: (1) geochemical surveys sampling surface and near-surface transported regolith are capable of identifying major lithologies and mineralization below the cover; and (2) a sampling strategy targeting outlet sediments of large catchments allows the application of ultra-low sampling densities in Australia. These findings overcome the main hurdles met by earlier attempts at designing a nation-wide geochemical survey. The strategy for the resulting National Geochemical Survey of Australia (NGSA) project, recently approved for funding under the Australian Government's Onshore Energy Security Initiative, is outlined. By 2011, the NGSA will produce a publicly available multi-element, internally consistent and state-of-the-art regolith geochemical database and atlas to support decision-makers.