Water storage for later use is essential for Kingdom of Saudi Arabia, KSA, as there are no natural surface water resources. The main natural water resources in KSA are ground water and rain water falling only in some provinces. Water is stored mainly by dams. Al-Baha province is located on the western south of Kingdom of Saudi Arabia, KSA. Water resources and uses in KSA and Al-Baha are reviewed. Data are collected for fourteen dams that were constructed for water storage during the period from 2008 to 2012. The data is tabulated ascending according to the water storage. The purposes and the types of dams storing water in Al-Baha province are reviewed. The cost (in Saudi Riyal) is plotted versus the water storage (in m3) for the fourteen dams. Then regression analyses are done employing micro soft excel software. It is obvious that the value of water storage of 4 millions m3 is significant with respect to the associated cost. Optimum water storage for all types of dams can be accomplished reasonably for the value less than 4 millions m3. Otherwise the type of the dam has to be taken into consideration for optimum water storage. Optimum water storage for earth fill dams is achieved. Also for concrete dams optimum water storage is fixed for both less than and more than the significant value of 4 millions m3. Equations are obtained to predict the cost of the required dams for optimum water storage.