High surface area, self-organized nanoporous ZrO2 arrays with perfect adhesion to the Zr substrate were synthesized by anodization in an aqueous electrolyte containing (NH4)2SO4 and NH4F. The obtained semiconductor materials were tested as photocatalysts for decolorization of the methyl red (MR) as a model azo dye pollutant. It was demonstrated that as-synthesized anodic ZrO2 anodic layers are already crystalline and, therefore, do not require further thermal treatment to provide a high photocatalytic performance. However, photocatalytic efficiency could be improved by annealing at a relatively low-temperature of 350 °C. Higher annealing temperatures caused a gradual drop of photocatalytic activity. The photocatalytic behavior was correlated with the crystal phase transformation in anodic ZrO2. It was found that higher photocatalytic activity was observed for the tetragonal phase over the monoclinic phase (predominant at elevated temperatures). It results from the optimal and complex electronic structure of annealed ZrO2 with three different energy states having absorption edges at 2.0, 4.01 and 5.28 eV.