Supplying desalination plants from renewable resources is a promising solution to overcome water scarcity. Currently, these alternative sources of energy have attracted more attention due to the intensified energy crisis. Since having relatively higher costs, defining an optimal investment plan ensures the cost-effectiveness of the whole system. In previous studies, the desalination unit’s size was often considered constant, and power supply components were optimized by minimizing Net Present Cost. An optimized system based on this cost term does not reflect the actual cost of produced water. This paper presents a new configuration and linear formulation for optimal renewable energy-powered water desalination planning. In the proposed model, the size of both the desalination unit and the supply system components are variable and optimized simultaneously by minimizing the Levelized Cost of Water. The water and energy storage are also considered and optimized while emitted carbon by the system is controlled. Besides, a comprehensive sensitivity analysis is performed by changing system configuration, renewable potential, yearly emission cap, desalination unit parameters, and supply system per unit costs. Besides constituting a reliable optimization framework, the study results detect the most influential factors and reveal a future roadmap to further water cost analysis and reduction.