The histidine protein (HPr) is the energy-coupling protein of the phosphoenolpyruvate (PEP)-dependent carbohydrate:phosphotransferase system (PTS), which catalyzes sugar transport in many bacteria. In its functions, HPr interacts with a number of evolutionarily unrelated proteins. Mainly, it delivers phosphoryl groups from enzyme I (EI) to the sugar-specific transporters (EIIs). HPr proteins of different bacteria exhibit almost identical structures, and, where known, they use similar surfaces to interact with their target proteins. Here we studied the in vivo effects of the replacement of HPr and EI of Escherichia coli with the homologous proteins from Bacillus subtilis, a gram-positive bacterium. This replacement resulted in severe growth defects on PTS sugars, suggesting that HPr of B. subtilis cannot efficiently phosphorylate the EIIs of E. coli. In contrast, activation of the E. coli BglG regulatory protein by HPr-catalyzed phosphorylation works well with the B. subtilis HPr protein. Random mutations were introduced into B. subtilis HPr, and a screen for improved growth on PTS sugars yielded amino acid changes in positions 12, 16, 17, 20, 24, 27, 47, and 51, located in the interaction surface of HPr. Most of the changes restore intermolecular hydrophobic interactions and salt bridges normally formed by the corresponding residues in E. coli HPr. The residues present at the targeted positions differ between HPrs of gram-positive and -negative bacteria, but within each group they are highly conserved. Therefore, they may constitute a signature motif that determines the specificity of HPr for either gram-negative or -positive EIIs.