In order to study the fatigue performance of a steel bridge deck and a vertical stiffener connection fillet weld, a mechanical vibration fatigue testing machine was used to test nine specimens with constant amplitude fatigue loading, and the fatigue performance of the welds of the specimens was evaluated with two methods, the nominal stress and hot spot stress methods. The test results show that, under the fatigue load, the specimens’ fatigue crack initiation occurs on the weld toe, and then the cracks grow along the weld toe and finally extend in bilateral symmetrical manner along the plate transverse, which is perpendicular to the weld edge. With the nominal stress method, the test results are above the S-N curve in JSSC-G, which has a fatigue strength of 50 MPa. With the hot spot stress method, the test results are above the S-N curve in Eurocode 3 specification, which has a fatigue strength of 100 MPa. The results suggest that the fatigue strength of the fillet weld of the test specimens’ fatigue details should be set at 50 MPa for nominal stress and 100 MPa for hot spot stress.