The anti-diabetic drug metformin is one of the most widely prescribed medicines in the world. Together with its degradation product guanylurea, it is a major pharmaceutical pollutant in wastewater treatment plants and surface waters. An operon comprising two genes of the ureohydrolase family in Pseudomonas and Aminobacter bacteria has recently been implicated in metformin degradation. However, the corresponding proteins have not been characterized. Here we show that these genes encode a Ni2+-dependent enzyme that efficiently and specifically hydrolyzed metformin to guanylurea and dimethylamine. The active enzyme is a heteromeric complex of α- and β- subunits in which only the α-subunits contain the conserved His and Asp residues for the coordination of two Ni2+ ions in the active site. A crystal structure of metformin hydrolase revealed an α2β4 stoichiometry of the hexameric complex, which is unprecedented in the ureohydrolase family. By studying a closely related but more widely distributed enzyme, we found that the putative predecessor specifically hydrolyzed dimethylguanidine instead of metformin. Our findings establish the molecular basis for metformin hydrolysis to guanylurea as the primary pathway for metformin biodegradation and provide insight into the recent evolution of ureohydrolase family proteins in response to an anthropogenic compound.