Organohalide-respiring microorganisms can use a variety of persistent pollutants, including trichloroethene (TCE), as terminal electron acceptors. The final two-electron transfer step in organohalide respiration is catalyzed by reductive dehalogenases. Here we report the x-ray crystal structure of PceA, an archetypal dehalogenase from Sulfurospirillum multivorans, as well as structures of PceA in complex with TCE and product analogs. The active site harbors a deeply buried norpseudo-B-12 cofactor within a nitroreductase fold, also found in a mammalian B-12 chaperone. The structures of PceA reveal how a cobalamin supports a reductive haloelimination exploiting a conserved B-12-binding scaffold capped by a highly variable substrate-capturing region.