Abstract: This study investigates the size-dependent mechanical behavior of the HfNbTaTiZr refractory high-entropy alloy (RHEA) under uniaxial tension, with a focus on the effects of random solid-solution (RSS) and local chemical order (LCO). A machine learning framework is developed to accelerate the parameterization of interatomic force fields (FFs), enabling molecular dynamics simulations of three nanocrystalline models: (i) a meta-atom (MA) model representing the RHEA as a hypothetical single-element system with averaged properties, (ii) a quinary RSS model with randomly distributed constituent atoms, and (iii) a Monte Carlo (MC) model with internal LCO. The results reveal that RSS enhances strength, while LCO reduces flow stress level but improves strain hardening and failure resistance. A transition from Hall-Petch (HP) strengthening to inverse Hall-Petch (IHP) softening is observed, with LCO suppressing this transition. The associated plastic mechanisms (i.e., dislocation slip, deformation twinning, phase transformation and grain boundary movements) are analyzed from both nanostructural and energetic perspectives. Theoretical models are established to describe the size-dependent yield strength and estimate the critical grain size. Additionally, the contributions of different plastic mechanisms to the overall stress response are separately quantified. These findings provide new insights into the design and performance optimization of RHEAs through nanostructural engineering.