Central receiver solar power plants are becoming an increasingly important technology worldwide and appear to be well suited to areas with moderate to high solar availability in Australia. However, the lack of large commercial installations in Australia results in a heavy reliance on cost and performance data from international literature when assessing possible installations. High variability in costs was found and, in combination with solar variability, this leads to considerable uncertainty when estimating the cost of electricity for potential projects. A stochastic methodology is presented that allows for changes in size of the plant, storage capacity, site location, costs of different plant items, and performance variations over the plant's lifetime. The developed methodology is used to produce a distribution of LCOE estimates. Three Australian sites, namely Alice Springs, Kalgoorlie and Mildura, are used as examples to examine the impact of changes of multiple variables on LCOE estimates. Analysis of these case studies shows a limited influence of storage capacity on LCOE, but considerably higher dependence on plant size and site selection. This suggests that the methodology could be applied to select an optimum plant design to meet specific targets or to compare the benefits of prospective projects at different sites.