The influence of the temperature and sort of alloying element on the deformation of the nanocrystalline (NC) binary Al alloys with segregation of 10.2 at % Ti, Co, or Mg over grain boundaries has been studied using the molecular dynamics. The deformation behavior of the materials has been studied in detail by the simulation of the shear deformation of various Al bicrystals with the grain-boundary segregation of impurity atoms, namely, Ti, Co, or Mg. The deformation of bicrystals with different grain orientation has been studied. It has been found that Co introduction into grain boundaries of NC Al has a strengthening effect due to the deceleration of the grain-boundary migration (GBM) and difficulty in the grain-boundary sliding (GBS). The Mg segregation at the boundaries greatly impedes the GBM, but stimulates the development of the GBS. In the NC alloy of Al–Ti, the GBM occurs actively, and the flow-stress values are close to the values characteristic of pure Al.