The long exposure of structural components to high temperatures (above 600 °C) negatively changes their mechanical properties, severely compromising the structural capacity of buildings and other structures in which safety is a primary concern. Developing new cheaper fire-resistant steels with better mechanical and thermal performances represents a challenging, cutting-edge materials science and engineering research topic. Alloying elements such as Nb and Mo are generally used to improve the strength at both room and high temperatures due to the formation of precipitates and harder microconstituents. This study shows that adding small amounts of boron in Nb-microalloyed fire-resistant steels may be crucial in maintaining mechanical properties at high temperatures. The widely used 66% yield-strength criteria for fire resistance was achieved at ≈574 °C for the B-added alloys. In contrast, for those without boron, this value reached ≈460 °C, representing a remarkable boron-induced mechanical strengthening enhancement. First-principles quantum mechanics calculations demonstrate that boron additions can lower 11.7% of the vacancy formation energy compared to pure ferrite. Furthermore, for Nb-added steels, the reduction in the vacancy formation energy may reach 33.2%, suggesting that the boron-niobium combination could act as an effective pinning-based steel-strengthening agent due to the formation of B-induced higher-density vacancy-related crystalline defects, as well as other well-known steel strengthening mechanisms reported in the literature. Adding boron and niobium may, therefore, be essential in designing better structural alloys.