In bacteria that live in hosts whose terminal sugar is a sialic acid, Glucosamine-6-phosphate deaminase (NagB) catalyzes the last step in converting sialic acid into Fructose-6-phosphate. These bacteria then use the Fructose-6-phosphate as an energy source. The enzyme NagB exists as a hexamer in Gram-negative bacteria and is allosterically regulated. In Gram-positive bacteria, it exists as a monomer and lacks allosteric regulation. Our identification of a dimeric Gram-negative bacterial NagB motivated us to characterize the structural basis of two closely related oligomeric forms. We report here the crystal structures of NagB from two Gram-negative pathogens, Haemophilus influenzae (Hi) and Pasturella multocida (Pm). The Hi-NagB is active as a hexamer, while Pm-NagB is active as a dimer. Both Hi-NagB and Pm-NagB contain the C-terminal helix implicated as essential for hexamer formation. The hexamer is described as a dimer of trimers. In the Pm-NagB dimer, the dimeric interface is conserved. The conservation of the dimer interface suggests that the three possible oligomeric forms of NagB are a monomer, a dimer, and a trimer of dimers. Computational modeling and MD simulations indicate that the residues at the trimeric interface have less stabilizing energy of oligomer formation than those in the dimer interface. We propose that Pm-NagB is the evolutionary link between the monomer and the hexamer forms.