APS reductase catalyzes the first committed step of reductive sulfate assimilation in pathogenic bacteria, including Mycobacterium tuberculosis, and is a promising target for drug development. We report the 2.7 A resolution crystal structure of Pseudomonas aeruginosa APS reductase in the thiosulfonate intermediate form of the catalytic cycle and with substrate bound. The structure, high-resolution Fourier transform ion cyclotron resonance (FT-ICR) mass spectrometry, and quantitative kinetic analysis, establish that the two chemically discrete steps of the overall reaction take place at distinct sites on the enzyme, mediated via conformational flexibility of the C-terminal 18 residues. The results address the mechanism by which sulfonucleotide reductases protect the covalent but labile enzyme-intermediate before release of sulfite by the protein cofactor thioredoxin. P. aeruginosa APS reductase contains an [4Fe-4S] cluster that is essential for catalysis. The structure reveals an unusual mode of cluster coordination by tandem cysteine residues and suggests how this arrangement might facilitate conformational change and cluster interaction with the substrate. Assimilatory 3'-phosphoadenosine 5'-phosphosulfate (PAPS) reductases are evolutionarily related, homologous enzymes that catalyze the same overall reaction, but do so in the absence of an [Fe-S] cluster. The APS reductase structure reveals adaptive use of a phosphate-binding loop for recognition of the APS O3' hydroxyl group, or the PAPS 3'-phosphate group.