HisA is a (βα)8 barrel enzyme that catalyzes the Amadori rearrangement of N'-[(5'-phosphoribosyl)formimino]-5-aminoimidazole-4-carboxamide ribonucleotide (ProFAR) to N'-((5'-phosphoribulosyl) formimino)-5-aminoimidazole-4-carboxamide-ribonucleotide (PRFAR) in the histidine biosynthesis pathway, and it is a paradigm for the study of enzyme evolution. Still, its exact catalytic mechanism has remained unclear. Here, we present crystal structures of wild type Salmonella enterica HisA (SeHisA) in its apo-state and of mutants D7N and D7N/D176A in complex with two different conformations of the labile substrate ProFAR, which was structurally visualized for the first time. Site-directed mutagenesis and kinetics demonstrated that Asp-7 acts as the catalytic base, and Asp-176 acts as the catalytic acid. The SeHisA structures with ProFAR display two different states of the long loops on the catalytic face of the structure and demonstrate that initial binding of ProFAR to the active site is independent of loop interactions. When the long loops enclose the substrate, ProFAR adopts an extended conformation where its non-reacting half is in a product-like conformation. This change is associated with shifts in a hydrogen bond network including His-47, Asp-129, Thr-171, and Ser-202, all shown to be functionally important. The closed conformation structure is highly similar to the bifunctional HisA homologue PriA in complex with PRFAR, thus proving that structure and mechanism are conserved between HisA and PriA. This study clarifies the mechanistic cycle of HisA and provides a striking example of how an enzyme and its substrate can undergo coordinated conformational changes before catalysis.