This paper presents a fatigue criterion based on stress invariants for the frequency-based analysis of multiaxial random stresses. The criterion, named “Projection-by-Projection” (PbP) spectral method, is a frequency-based reformulation of its time-domain definition. In the time domain PbP method, a random stress path is first projected along the axes of a principal reference frame in the deviatoric space, thus defining a set of uniaxial random stress projections. In the frequency-domain approach, the damage of stress projections is estimated from the stress PSD matrix. Fatigue damage of the multiaxial stress is next calculated by summing up the fatigue damage of every stress projection. The criterion is calibrated on fatigue strength properties for axial and torsion loading. The calculated damage is shown to also depend on the relative ratio of hydrostatic to deviatoric stress components. The frequency-based multiaxial analysis of an L-shaped steel beam excited by a random input acceleration is proposed as an illustrative example. A finite element (FE) spectrum analysis is used to compute the stress PSD matrix at every node in the structure. Then, the local multiaxial fatigue damage is estimated by the proposed PbP criterion. A comparison with the “equivalent von Mises stress” approach by Preumont et al. (1994) is also presented The influence of different SN parameters for axial and torsion loading is critically discussed. The example emphasizes that PbP spectral method could be a very efficient and accurate tool for durability assessment of complex structures under multiaxial random loadings.