The long external filament of bacterial flagella is composed of several thousand copies of a single protein, flagellin. Here, we explore the role played by lysine methylation of flagellin in Salmonella, which requires the methylase FliB. We show that both flagellins of Salmonella enterica serovar Typhimurium, FliC and FljB, are methylated at surface-exposed lysine residues by FliB. A Salmonella Typhimurium mutant deficient in flagellin methylation is outcompeted for gut colonization in a gastroenteritis mouse model, and methylation of flagellin promotes bacterial invasion of epithelial cells in vitro. Lysine methylation increases the surface hydrophobicity of flagellin, and enhances flagella-dependent adhesion of Salmonella to phosphatidylcholine vesicles and epithelial cells. Therefore, posttranslational methylation of flagellin facilitates adhesion of Salmonella Typhimurium to hydrophobic host cell surfaces, and contributes to efficient gut colonization and host infection.