Addition of solutes is commonly used to stabilize nanocrystalline materials against grain growth. However, segregating at grain boundaries, these solutes also affect the process of dislocation nucleation from grain boundaries under applied stress. Using atomistic simulations we demonstrate that the effect of solutes on the dislocation nucleation strongly depends on the distribution of solutes at the grain boundary, which can vary dramatically depending on the solute type. In particular, our results indicate that the solutes with a smaller size mismatch can be more effective in suppressing dislocation emission from grain boundaries. Bearing in mind that dislocation slip originating from grain boundaries or their triple junctions is the dominant mechanism of plastic deformation when grain sizes are reduced to the nanoscale, we emphasize the importance of the search for the optimal solute additions, which would stabilize the nanocrystalline material against grain growth and, at the same time, effectively suppress the dislocation nucleation from the grain boundaries.