Microaerophilic pathogens such as Giardia lamblia, Entamoeba histolytica, and Trichomonas vaginalis have robust oxygen consumption systems to detoxify oxygen and maintain intracellular redox balance. This oxygen consumption results from H2O-forming NADH oxidase (NOX) activity of two distinct flavin-containing systems: H2O-forming NOXes and multicomponent flavodiiron proteins (FDPs). Neither system is membrane bound, and both recycle NADH into oxidized NAD+ while simultaneously removing O2 from the local environment. However, little is known about the specific contributions of these systems in T. vaginalis. In this study, we use bioinformatics and biochemical analyses to show that T. vaginalis lacks a NOX-like enzyme and instead harbors three paralogous genes (FDPF1-3), each encoding a natural fusion product between the N-terminal FDP, central rubredoxin (Rb), and C-terminal NADH:Rb oxidoreductase domains. Unlike a "stand-alone" FDP that lacks Rb and oxidoreductase domains, this natural fusion protein with fully populated flavin redox centers directly accepts reducing equivalents of NADH to catalyze the four-electron reduction of oxygen to water within a single polypeptide with an extremely high turnover. Furthermore, using single-particle cryo-EM, we present structural insights into the spatial organization of the FDP core within this multidomain fusion protein. Together, these results contribute to our understanding of systems that allow protozoan parasites to maintain optimal redox balance and survive transient exposure to oxic conditions.