Water pollution derived from organic pollutants is one of the global environmental problems. The Fenton reaction using Fe2+ as a homogeneous catalyst has been known as one of clean methods for oxidative degradation of organic pollutants. Here, a layered double hydroxide (Fe2+Al3+-LDH) containing Fe2+ and Al3+ in the structure was used to develop a “heterogeneous” Fenton catalyst capable of mineralizing organic pollutants. We found that sulfate ion (SO42−) immobilized on the Fe2+Al3+-LDH significantly facilitated oxidative degradation (mineralization) of phenol as a model compound of water pollutants to carbon dioxide (CO2) in a heterogeneous Fenton process. The phenol conversion and mineralization efficiency to CO2 reached >99% and ca. 50%, respectively, even with a reaction time of only 60 min.