With the advancement of modern industry, further improvement of the strength of high-strength steels is highly required without compromising their resistance to hydrogen-induced delayed fracture (HIDF). Quenching and tempering is the most convenient and effective method for regulating the HIDF performance of high-strength steels along with their mechanical properties, when their chemical composition is fixed. In addition to tempering temperature, tempering time can influence the HIDF performance of high-strength steels by controlling their microstructural characteristics. Herein, the effect of high-temperature tempering time (t_temp) at 600 °C on the HIDF behavior of a medium-carbon Cr–Ni–Mo–V-type high-strength bolt steel was investigated through slow strain rate tensile tests using pre-hydrogen-charged notched round bar specimens. The results reveal that when t_temp is extended from 2 to 6 h, the size of the nanoscale plate-like V-rich MC precipitates remains almost unchanged, and when t_temp is further extended to 24 h, a considerable increase in size is observed. The hardness and strength of the experimental steel first increase and then decrease with increasing t_temp, with a peak at t_temp = 2 h. Further theoretical calculations reveal that precipitation strengthening and dislocation strengthening are the dominant factors causing the differences in the strength of the experimental steel tempered at different t_temp. The HIDF resistance, characterized by the notch tensile strength (NTS_H) of hydrogen-charged samples, decreases exponentially as the diffusible hydrogen content (H_D) increases. At the same H_D level, NTS_H increases gradually in the order of 2, 24, and 6 h tempered samples, whereas the hydrogen embrittlement susceptibility index, characterized by the relative notch tensile strength loss ratio, decreases gradually in the same order. Furthermore, the critical hydrogen content H_C, defined as the H_D corresponding to 90% of the notch tensile strength of the un-hydrogen-charged sample, gradually increases in the order of 2, 24, and 6 h tempered samples. This indicates that the 6 h tempered sample exhibits the greatest resistance to HIDF, the highest hydrogen tolerance, and the lowest susceptibility to hydrogen embrittlement. Further hydrogen thermal analysis and hydrogen permeation test results reveal that the experimental steel exhibits the strongest hydrogen trapping capability and the lowest hydrogen permeation coefficient at t_temp = 6 h. In conclusion, changes in the hydrogen trapping characteristics of the V-rich MC precipitates with t_temp are the main reason for the changes in the HIDF performance of the experimental steel. Therefore, selecting an appropriate t_temp allows the attainment of the desired strength level and helps achieve excellent resistance to HIDF.