—As a common mineral phase on Earth and Martian regolith, natural rutile was reported as a potential candidate for use as a Fenton catalyst in this study. The influences of Fe and V in various chemical states on the generation of reactive oxygen species (ROSs) and the catalytic activity of rutile were examined. A series of rutile samples with various surface and bulk states of Fe and V were obtained initially by hydrogen annealing of natural rutile at ~773–1173 K. X-ray diffraction, electron paramagnetic resonance spectra, and X-ray photoelectron spectroscopy demonstrated that the atomic fractions of Fe(III) and V(V) decreased sharply with increasing temperature, along with the accumulation of surface Fe(II) and bulk V(III). All as-prepared materials showed enhanced Fenton degradation efficiency on methylene blue (MB) compared with P25-TiO2, and the treated samples exhibited up to 3.5-fold improvement in efficiency at pH 3 compared to the untreated sample. The improved efficiency was attributed mainly to Fenton catalysis involving Fe(II) and V(III). The dissolved Fe2+ played a crucial role in the homogeneous Fenton reaction, while the bound V(III) favored adsorption primarily and may have facilitated heterogeneous Fenton reaction and the regeneration of Fe2+. The pH regulated the reaction mechanism among homogeneous (pH = 3) and heterogeneous (pH = 3.7) Fenton catalysis and physical adsorption (pH = 5, 6). The aim of the present study was to improve the understanding of the potential role of natural rutile with advanced oxidation functions in Earth systems and even on Mars, which also provide an inspiration for screening natural rutile and any other similar, Earth-abundant, low-cost minerals for environmental application.