A simple method to obtain a highly refractory HfB2-based ceramic nano-composite is presented. The boride was hot pressed with additions of SiC and WC particles and subsequently annealed at 2100 °C for 2 h. The annealing procedure was beneficial for high temperature strength, which increased by about 300 MPa in the 1500 °C-1800 °C temperature range compared to the as-sintered material. Peak strengths of 850 MPa at 1500 °C and 650 MPa at 1800 °C were achieved due to two main microstructural changes. First, rounded SiC particles that were surrounded by a silica-based glass in the as-sintered ceramics evolved into platelets with mostly clean grain boundaries after heat treatment. In addition, the (Hf,W)B2 solid solution that formed as shells around HfB2 grain cores during densification reached an equilibrium state after annealing that revealed nano-texturing of the shell, which constituted a nano-composite with metallic W nano-particles embedded within HfB2 grains. These two features combined to contribute to refractoriness and increased strength at elevated temperature. The unique findings reported in this study launch significant opportunities for ceramic development, manufacturing, and applications.