High tension bolts in critical joints in internal combustion engines are susceptible to fatigue failure. Computer-aided bolted joint design procedures require knowledge of the dependence of bolt fatigue limit on the mean stress and ultimate tensile strength. This dependence is investigated with staircase fatigue limit tests. The test results show that when the bolt fatigue limit is estimated with the nominal stress of the bolt, it decreases with increasing tensile strength and nominal mean stress. However, there is a range of the nominal mean stress where the bolt fatigue limit is almost constant. The test results are interpreted with finite element analysis.