Multiple interstitial elements (B, C and O), were incorporated into a body-centred cubic (BCC) FeMnCoCr-based interstitial high entropy alloy (iHEA). While achieving an impressive yield strength of 2.55 GPa, the new alloy also possesses appreciable ductility under mechanical loading. The unusual combination of hardening effects brought about by interstitial atoms, compositional fluctuations, and fine grain size greatly strengthened the alloy by inhibiting dislocation motion. Moreover, interstitial elements helped reinforce the grain boundaries through segregation and also assisted in tuning the phase stability. The new alloy transformed from the BCC to hexagonal closed-packed (HCP) phase initially. With increasing load the HCP phase was gradually converted into face-centred cubic (FCC); the resultant HCP/FCC nanolaminates enhanced plasticity via strain partitioning. Under higher loads, the FCC phase became dominant, giving rise to deformation twinning. Taken together, the newly developed BCC structured iHEA affords not only high strength, but also confers remarkable ductility through multiple deformation pathways.