Desalination of water can be achieved via the use of solar stills, especially as they are considered to be the cheapest option for potable water production in remote, arid and small communities with limited availability of freshwater. However, one very common challenge with water production via solar stills is that the amount of water produced is usually low. The aim of this work is to evaluate the productivity enhancement of solar stills using different heat storage materials in the basin. To conduct the experiments, three triangular solar stills were fabricated with similar shapes. In each solar still, a transparent polythene film and a stainless steel trough as cover and basin were used, respectively. Each basin had a length of 50 cm, width of 30 cm and depth of 8 cm. The solar still configurations differed based on inclusion of 2 cm depth of black soil or a layer of black paint in the basin. Experimental outputs indicated that there was significant increase in the amount of potable water produced using different heat storage materials under Malaysia tropical condition. Daily cumulative results of water production using these solar stills showed that the solar still with black-painted basin was more efficient; its level of productivity over the conventional solar still and the solar still with black soil in basin was 101 and 20 , respectively. Some water quality parameters were also tested in the laboratory which indicated that the treated water met the WHO standard for drinking water. © 2015, The Author(s).