Welded structures under random loading are susceptible to fatigue-induced failure, posing significant economic and safety risks. However, accurately predicting these structures' fatigue damage and life remains challenging due to the limitations associated with the traditional weld stress extrapolation methods, such as nominal, hotspot, and notch stress methods. These methods struggle with precisely defining and characterizing the stresses at the weld toe and root, as they vary depending on factors like weld stress concentration effects, joint geometry, and loading modes. Consequently, there is a need for a fatigue analysis approach that employs a more robust and reliable stress evaluation method, leading to significantly improved accuracy in predicting the fatigue damage and life of welded structures under random fatigue loading conditions. This research introduces an Equilibrium Equivalent Structural Stress (EESS)-based frequency domain fatigue analysis approach for welded structures subjected to random loading. The proposed method utilizes the EESS formulations, which are based on the decomposition and characterization of weld toe stresses with a single stress parameter, together with incorporating structural dynamic properties' effects on the stresses acting on the weld joints and the corresponding accumulated fatigue damage of the structure. Numerical demonstration and validation of the proposed method have been performed using a welded Rectangular Hollow Section (RHS) T-joint structure subjected to a stationary random fatigue load. The proposed method's fatigue damage and life results are compared with fatigue test data and the equivalent hotspot stress extrapolation-based technique. The EESS-based frequency domain fatigue analysis method accurately predicts fatigue crack initiation locations, consistent with literature findings. It also demonstrates a 26% improvement in fatigue life prediction compared to the hotspot method. Furthermore, the proposed method achieved a maximum computational efficiency gain of 58% compared to the alternative hotspot stress-based fatigue analysis method.