Refractory High Entropy Alloys (RHEAs) are advanced materials suitable for high-temperature applications due to their remarkable properties, such as excellent strength, ductility, wear resistance, among others. In this study, the effect of temperature on the mechanical properties of the nanocrystalline bcc HfNbTaZr RHEA is explored under uniaxial loading using molecular dynamics simulations. Temperatures and grain sizes in the range of 100–1200 K and 5–17 nm are considered here. Our results showed that the highest yield strengths and flow stress were achieved in the 10–15 nm range for grain sizes, where the transition from Hall-Petch (HP) to the inverse Hall-Petch (iHP) effect was clearly observed at low temperatures, with a weaker grain size dependence in the HP regime at high temperatures. The MD results align extremely well with a scaling model for the elastic modulus as a function of temperature, and with a strength model which have been extensively employed to understand experimental results up to high temperatures, but the reference strain-rate has to be adjusted to take into account the large values for atomistic simulations. These models are typically based on relatively simple scenarios, like the motion of single straight dislocations, either edge or screw, and lack of dislocation junctions and twinning. Here, deformation includes both edge and screw dislocations, dislocation junctions, grain boundary plasticity, twinning, etc., but the general trend of smooth softening with temperature is observed despite the complex scenario. Some models assume that plasticity in RHEAs would be controlled by edge dislocations but, under the simulated conditions, there are contributions from both edge and screw dislocations. In addition, we quantify twin volume-fraction and find a transition from twin-dominated deformation to dislocation-dominated deformation as temperature increases, with twinning increasing for larger grains. Our results provide quantification of the mechanical properties and plasticity of a nanocrystalline bcc RHEA up to high temperatures, and the proposed adaptation of a strength model allows connection between typical experiments and high strain rate simulations.