Fire resistance of structural steels used in buildings is typically evaluated based on the ratio of the yield strength at 600 °C to that at room temperature. Fire-resistant steel shows a yield strength ratio of more than 2:3 between 600 °C and room temperature and achieves an excellent high-temperature strength. Alloying elements such as Mo and Nb are used to improve the strength at elevated temperatures. In this study, the effects of the addition of Mo and Nb on the fire resistance of steel were carefully investigated using SEM, TEM, in-situ TEM, EPMA, 3D-APT, positron annihilation lifetime spectroscopy, and first principles calculations. The fire resistance in Mo and Nb added steel (Mo + Nb) was shown to be drastically improved compared to plain carbon steel (CMn). The improvement in the high-temperature strength in Mo + Nb was attributed to the precipitation of fine Nb-rich MX particles and a solid solution of Mo and Nb hindering the dislocation movement, and thereby minimizing the dislocation annihilation at elevated temperature. The solid solution of Mo and Nb lowers the vacancy formation energy and allows a vacancy to form more easily, leading to a large lattice distortion which results in a slower dislocation mobility in Mo + Nb.