SI property class 12.9 high strength steel bolts were used to investigate the fatigue behavior of bolt threads rolled before/after heat treatment using two different thread profiles and five different preload values. Bolts were 3/8 UNRC-16 (coarse) and 3/8 UNRF-24 (fine) and preloads were taken as 1, 50, 75, 90, and 100% of roll before heat treatment proof stress. Maximum near surface residual compressive stresses, obtained via x-ray diffraction, ranged from -500 to -1000 MPa. Axial loads were applied through the nut and all fatigue failures occurred at the first thread of the nut/bolt interface. SEM evaluation indicated all fatigue crack growth regions contained multiple fatigue facets, while final fracture regions were ductile dimples. The fatigue resistance of both the fine and coarse threads rolled after heat treatment with preload stresses of 1% (R-ratio less than 0.05) caused very large increases in 107 cycles fatigue strength (158 and 147% respectively) compared to roll before heat treatment. However, with higher preload stresses, the coarse thread fatigue strength had no increases. The fine thread roll after heat treatment bolts when tested at the higher proof loads had 107 fatigue strengths of 69 to 30% increase. These increases are much less than the 158% at 1% preload, but still significant. The results indicate the importance of evaluating bolt fatigue strengths at representative high preload values.