The presence of internal hydrogen through cathodic charging has substantial influence on the near-threshold fatigue behavior of an HSLA steel with an as-received yield strength of 365 MPa. The results of fatigue crack propagation tests in both as-received and heat-treated conditions indicate higher crack propagation rates and lower threshold stress intensities in the presence of internal hydrogen. These effects are dependent on strength, mean stress or R-ratio, and test temperature. The enhancement in the crack propagation process is more severe in the higher strength material and at higher mean stress. An unusual behavior was observed due to decreasing test temperature from 300 to 123 K in which higher thresholds and lower crack propagation rates at 233 and 173 K were obtained in the presence of internal hydrogen. These effects are a result of true intrinsic hydrogen enhanced fracture and deformation processes.