This paper presents an experimental investigation of the mechanical properties of sixty A4-70 and A4-80 stainless steel bolts under steady-state temperatures ranging from 20 to 900 °C. The material responses at elevated temperatures of the parent materials, SUS316 and SUS316Ti stainless steels (also known as EN 1.4401 and EN 1.4571 steels), and of fire-resistant bolts are included for comparisons. The tensile strength degradation of stainless steel bolts in fire are found to be reasonably close to those specified by Eurocode 3 Part 1.2 for their parent materials, but the Young's modulus degradation is not so robust. At temperatures lower than 650 °C, the stainless steel bolts retain their 0.2% proof strength better than their parent materials. Importantly, in the temperature range of 500 to 900 °C the stainless steel bolts retain their tensile strength, Young's modulus and 0.2% proof strength better than fire-resistant bolts (BOLTEN110N-FR to JSSII-09 standard). Based on the experimental data, reduction factors for tensile strength, Young's modulus and 0.2% proof strength are derived in this paper for stainless steel bolts at elevated temperatures.