When grain sizes are reduced to the nanoscale, grain boundaries (GB) become the dominant sources of the dislocations that enable plastic deformation. We present the first molecular dynamics (MD) study of the effect of substitutional solutes on the dislocation nucleation process from GBs during uniaxial tensile deformation. A simple bi-crystal geometry is utilized in which the nucleation and propagation of dislocations away from a GB is the only active mechanism of plastic deformation. Solutes with atomic radii both larger and smaller than the solvent atomic radius were considered. Although the segregation sites are different for the two cases, both produce increases in the stress required to nucleate a dislocation. MD simulations at room temperature revealed that this increase in the nucleation stress is associated with changes of the GB structure at the emission site caused by dislocation emission, leading to increases in the heats of segregation of the solute atoms, which cannot diffuse to lower-energy sites on the timescale of the nucleation event. These results contribute directly to understanding the strength of nanocrystalline materials, and suggest suitable directions for nanocrystalline alloy design leading toward structural applications.