Least cost options are presented for supplying the Australian National Electricity Market (NEM) with 100% renewable electricity using wind, photovoltaics, concentrating solar thermal (CST) with storage, hydroelectricity and biofuelled gas turbines. We use a genetic algorithm and an existing simulation tool to identify the lowest cost (investment and operating) scenarios of renewable technologies and locations for NEM regional hourly demand and observed weather in 2010 using projected technology costs for 2030. These scenarios maintain the NEM reliability standard, limit hydroelectricity generation to available rainfall, and limit bioenergy consumption. The lowest cost scenarios are dominated by wind power, with smaller contributions from photovoltaics and dispatchable generation: CST, hydro and gas turbines. The annual cost of a simplied transmission network to balance supply and demand across NEM regions is a small proportion of the annual cost of the generating system. Annual costs are compared with a scenario where fossil fuelled power stations in the NEM today are replaced with modern fossil substitutes at projected 2030 costs, and a carbon price is paid on all emissions. At moderate carbon prices, which appear required to address climate change, 100% renewable electricity would be cheaper on an annual basis than the replacement scenario.