In this work, instrumented nanoindentation was employed to investigate the effect of interstitial oxygen or nitrogen addition on the incipient plasticity and dislocation nucleation in a body-centered cubic NbTiZrHf high-entropy alloy (HEA) at loading rates of 10–1000 µN/s. We conducted quantitative statistical analysis and density functional theory (DFT) calculations to identify the role of interstitial oxygen/nitrogen during the onset of plasticity. Synchrotron X-ray diffraction and transmission electron microscopy were also performed to confirm that the oxygen/nitrogen atoms were indeed present as interstitial solutes. These interstitial solutes could increase the critical shear stress required to initiate plasticity, and nitrogen yielded a larger hardening effect than oxygen. The activation volumes were evaluated to be about 2–3 atomic volumes, indicating cooperative migration of multiple atoms during the dislocation nucleation, and neither oxygen nor nitrogen appeared to significantly affect this activation process. Hardness tests were also carried out and the result demonstrated that the enhancement of the critical shear stress for incipient plasticity was not caused by the traditional solid-solution strengthening mechanism. DFT calculations revealed that oxygen/nitrogen interstitials induced local charge transfer and improved the lattice cohesion, which was probably responsible for the enhanced pop-in load/stress in the current interstitially alloyed HEAs.