This study shows the robustness of subsurface storage using sand dams under long-term climate change for the Kitui District in Kenya. Climate change is predicted to enhance potential evaporation through an increase in average temperature of about 3°C. Even though average precipitation will also increase, approximately 13%, the net water availability is projected to decrease in the future, about 1 and 34% in the seasons November to March and April to October, respectively. This study shows that under current climate conditions, total storage in the 500 sand dams currently developed in Kitui captures only 1.8 and 3.8% from the total runoff generated during the November–March and April–October seasons, respectively. These numbers increase to 3 and 20% of total available water for the year 2100 for the November–March and April–October seasons, respectively. Hence, downstream water shortages can be expected under climate change in the April–October season. An additional water consumption scenario has been developed in which 1000 new sand dams are developed. In this case, the percentage storage by 1500 sand dams relative to the total available water increases to about 11 and 60% for the November–March and April–October seasons, respectively. In general, the variability in runoff is projected to increase under climate change, and the probability of years in which there is significant water shortage will increase from about once every 30 yr to once every 10 yr.