Many attempts are made worldwide to create cheap, efficient, and eco-friendly water desalination systems. Passive solar stills (SS) are considered to be such. This paper presents the results of the experimental and theoretical investigation of the effects of using phase-change materials (PCM) on the performance of SS. The experiments were conducted for two paraffin waxes, as PCM and 1.0, 2.5, and 5.0 kg of PCM were used. The results of the experimental studies were used to validate a mathematical model, which was based on the energy balance ordinary differential equations. The equations were solved numerically since the approximate solutions obtained numerically are sufficient and relatively simple as compared to the exact analytical solutions. A theoretical analysis was then carried out and a novel and detailed dependence on the water evaporation rate as a function of water temperature and the difference between water and cover temperature was determined. It was also found that the productivity of the SS with PCM strongly depends on the operating conditions. For uniform initial temperatures of the SS, its productivity decreases with an increasing PCM-to-water mass ratio, and the maximum decrease is 10.8%. If the SS is not thermally insulated, the PCM can take the role of a thermal insulator and increase productivity by 1.1%, but there is an optimal PCM-to-water mass ratio. The greatest increase in productivity, by up to 47.1%, can be obtained when the PCM is heated outside the SS and inserted into the SS when the water temperature starts to decrease. In this case, the productivity increases with the increasing PCM-to-water mass ratio. These outcomes fill a knowledge gap caused by a lack of justification for why in some cases, the application of PCM fails to improve the productivity of SS.