N,N-dimethyl formamide (DMF) is an extensively used organic solvent but is also a potent pollutant. Certain bacterial species from genera such as Paracoccus, Pseudomonas, and Alcaligenes have evolved to use DMF as a sole carbon and nitrogen source for growth via degradation by a dimethylformamidase (DMFase). We show that DMFase from Paracoccus sp. strain DMF is a halophilic and thermostable enzyme comprising a multimeric complex of the α β or (α β ) type. One of the three domains of the large subunit and the small subunit are hitherto undescribed protein folds of unknown evolutionary origin. The active site consists of a mononuclear iron coordinated by two Tyr side-chain phenolates and one carboxylate from Glu. The Fe ion in the active site catalyzes the hydrolytic cleavage of the amide bond in DMF. Kinetic characterization reveals that the enzyme shows cooperativity between subunits, and mutagenesis and structural data provide clues to the catalytic mechanism.