There is a growing interest in High Entropy Alloys (HEAs) due to their outstanding mechanical properties. Most simulation studies have focused on face-centered cubic (fcc) HEAs; however, bcc HEAs can offer a larger elastic modulus and plastic yielding, thus, becoming possible candidates for the next generation of refractory materials. In this work, we focus on molecular dynamics (MD) simulations of bcc HfNbTaZr nanocrystalline samples, with a grain size (d) between 5 and 17 nm, deformed under tension at 300 K. The elastic modulus increases with the grain size and reaches a plateau near 10 nm. We find the typical inverse Hall–Petch (HP) behavior with yield strength, ultimate tensile stress (UTS), and flow stress increasing with d. Up to 12 nm, there are contributions from dislocations and twins; however, grain boundary (GB) activity dominates deformation. For the 5 nm grains, the GB disorder extends and leads to extensive amorphization and grain size reduction. For d>10 nm, there is a HP-type behavior with dislocations and twinning controlling deformation. For this regime, there is hardening at large strains. Compared to bcc single metal samples, the HP maximum of this HEA appears at a lower grain size, and this could be related to the chemical complexity facilitating dislocation nucleation. We use machine learning to help understand deformation regimes. We also compare our results to a single crystal (SC) HfNbTaZr HEA deformed along [001] and find that the single crystal is weaker than the nanocrystalline samples. The single crystal deforms initially by twinning and then rapidly by dislocation multiplication, leading to strong hardening. It has been proposed that edge dislocations play a major role in bcc HEA plasticity, and we also analyze the relative contributions of edge versus screw dislocations during deformation for both single crystal and nanocrystalline samples.