Salmonella exhibits 70 serologically distinct flagellins, used internationally to diagnose and track infections. The terminal sequences of flagellin protein subunits are conserved in a range of bacteria and are here used as evolutionary markers to reveal how new serotypes arise. Terminal sequences of flagellins that exhibit factors g or m (G-group) were distinct from other Salmonella antigens (Non-G-group) and cluster more closely with Escherichia coli. It is postulated that G-group flagellins were inherited from a common ancestor of E. coli and Salmonella and that these antigens were among the original set in Salmonella. Sequence differences at the 5′ termini may prevent recombination between co-infecting strains. Evidence of increased variation of flagellin in rare biphasic G-group serotypes suggests that the presence of a second flagellin locus allows mutation of the G-group flagellin. FljB probably arose from a single duplication of a Non-G gene, since which synonymous mutations resulted in the fljB-specific sequence at the 5′ termini.