Molecular dynamics is employed to study stress-strain curves obtained during high strain rate deformation of nanocrystalline Al-10.2 at.% Co alloy with (i) randomly distributed Co atoms (Al-Co substitutional solid solution) and (ii) Co atoms segregated in grain boundaries (GBs) of the alloy. The effect of Co distribution, deformation temperature, and the presence of hydrostatic pressure on the stress-strain relation is analyzed. The results are compared to that for nanocrystalline pure Al. It is found that the strength of the Al-Co solid solution is lower than that of the pure Al, while GB segregations of Co increase its strength. The alloys, regardless of the type of Co distribution, under shear loading with no hydrostatic pressure demonstrate higher ductility in comparison with the pure Al. The shear modulus of the Al-Co alloy with the GB segregations is noticeably larger than that of the pure Al and the Al-Co solid solution in a wide range of temperatures. The results of the study show that the GB segregations of Co can have a positive effect on the mechanical properties of nanocrystalline Al.