Iron oxide nanoparticles (FeONPs) prepared with plant extracts have been emerging as green and sustainable materials. FeONPs are usually amorphous due to the chelation of the tea polyphenols (TPs) to the iron, and the real nature of the iron compounds is not completely understood. The main goal of this study was to investigate the behavior of the green FeONPs synthesized from an Fe3+ salt and Cammelia sinensis (black tea) extract upon thermal treatment, in order to remove TPs and enable the formation of crystalline materials suitable for a thorough characterization and with the potential for diverse applications. The as-prepared FeONPs were assigned as mixed-valence Fe(III) oxyhydroxides and Fe(II)/Fe(III) ions bound to TPs. A detailed description of the phase transformation upon heating revealed the formation of the rare nano β-Fe2O3 phase at 400 °C, followed by a transformation to α-Fe2O3 as the temperature increased. Above 600 °C, the unprecedented formation of FePO4 and Fe3PO7 was observed, produced from the reaction of Fe2O3 and free phosphate ions present in the black tea leaves, Fe3PO7 being the major phase obtained at 900 °C. Finally, the catalytic potential of the FeONPs to treat the azo dye methyl orange through a heterogeneous Fenton-like system was investigated.