This paper presents the first detailed long-term stock turnover model to investigate scenarios to decarbonize the residential water heating sector in California, which is currently dominated by natural gas. We model a mix of water heating (WH) technologies including conventional and on-demand (tank-less) natural gas heating, electric resistance, existing electric heat pumps, advanced heat pumps with low global warming refrigerants and solar thermal water heaters. Technically feasible policy scenarios are developed by considering combinations of WH technologies with efficiency gains within each technology, lowering global warming potential of refrigerants and decreasing grid carbon intensity. We then evaluate energy demand, emissions and equipment replacement costs of the pathways. We develop multiple scenarios by which the annual greenhouse gas emissions from residential water heaters in California can be reduced by over 80% from 1990 levels resulting in an annual savings of over 10 Million Metric Tons by 2050. The overall cost of transition will depend on future cost reductions in heat pump and solar thermal water heating equipment, energy costs, and hot water consumption.