Due to their outstanding properties, ultra-fine-grained tungsten and its alloys are promising candidates to be used in harsh environments, hence it is crucial to understand their high temperature behavior and underlying deformation mechanisms. Therefore, advanced nanoindentation techniques were applied to ultra-fine-grained tungsten–rhenium alloys up to 1073 K. A continuous hardness decrease up to 0.2 Tm is rationalized by a still dominating effect of the Peierls stress. However, the absence of well-established effects of Rhenium alloying, resulting in a reduced temperature dependence of strength for coarse-grained microstructures, was interpreted as an indication for a diminishing role of kink-pair formation in ultra-fine-grained metals with sufficiently fine grain size. Despite slight grain growth in W, dislocation–grain boundary interaction was identified as the dominating deformation mechanism above 0.2 Tm. Interaction and accommodation of lattice dislocations with grain boundaries was affected by a reduced boundary diffusivity through alloying with Re.