The well-studied enterobacterium Escherichia coli present in the human gut can reduce trimethylamine N-oxide (TMAO) to trimethylamine during anaerobic respiration. The TMAO reductase TorA is a monomeric, bis-molybdopterin guanine dinucleotide (bis-MGD) cofactor-containing enzyme that belongs to the dimethyl sulfoxide reductase family of molybdoenzymes. We report on a system for the in vitro reconstitution of TorA with molybdenum cofactors (Moco) from different sources. Higher TMAO reductase activities for TorA were obtained when using Moco sources containing a sulfido ligand at the molybdenum atom. For the first time, we were able to isolate functional bis-MGD from Rhodobacter capsulatus formate dehydrogenase (FDH), which remained intact in its isolated state and after insertion into apo-TorA yielded a highly active enzyme. Combined characterizations of the reconstituted TorA enzymes by electron paramagnetic resonance spectroscopy and direct electrochemistry emphasize that TorA activity can be modified by changes in the Mo coordination sphere. The combination of these results together with studies of amino acid exchanges at the active site led us to propose a novel model for binding of the substrate to the molybdenum atom of TorA.