In the present work, modified embedded atom potential and large-scale molecular dynamics’ simulations were used to explore the effect of grain boundary (GB) segregated foreign interstitials on the deformation behavior of nanocrystalline (nc) iron. As a case study, carbon and nitrogen (about 2.5 at.%) were added to (nc) iron. The tensile test results showed that, at the onset of plasticity, grain boundary sliding mediated was dominated, whereas both dislocations and twinning were prevailing deformation mechanisms at high strain. Adding C/N into GBs reduces the free excess volume and consequently increases resistance to GB sliding. In agreement with experiments, the flow stress increased due to the presence of carbon or nitrogen and carbon had the stronger impact. Additionally, the simulation results revealed that GB reduction and suppressing GBs’ dislocation were the primary cause for GB strengthening. Moreover, we also found that the stress required for both intragranular dislocation and twinning nucleation were strongly dependent on the solute type