Deformation twinning creates a three-dimensional twin domain via the migration of forward, normal and lateral twin boundaries (TBs) with respect to twin shear direction, normal to twin plane and twin lateral direction. Solute segregation and pinning effect on the forward and normal TBs have been experimentally observed and demonstrated via atomistic simulations. Here, we conducted a comprehensive study of solute segregation and the pinning effect on the lateral TBs in Mg. First-principles density functional theory calculations were used to obtain the segregation and formation energies of 19 alloying elements in coherent regions of lateral TBs. Alloying elements with greater difference in atomic radius from Mg generally show more negative segregation energy. Moreover, alloying elements with good solubility are selected to demonstrate the pinning effect on a coherent interface. Ge, Ga, Y, Gd, La and Ca show negative segregation energy and solubility energy, indicating that these elements can form stable segregation and have a strong pinning effect at the lateral boundary. Molecular dynamics simulations revealed that solutes in coherent regions are more effective in pinning lateral TBs than those in misfit regions. The results provide insight into the selection of solute atoms for tailoring twinning behavior.