Many structures are subjected to random vibrations and those vibrations can cause a fatigue damage. So, to estimate the live time of the structure, we need to applied the fatigue multiaxial criteria at each point. Many studies demonstrate that the Sines criterion seems to give the best evaluation of the fatigue damage. But the application of this criterion need a high computing time if it's evaluated in the time domain. In this paper, we present a new methodology of calculation of the Local multiaxial fatigue damage, based on the formulation of the Sines criterion developed in the frequency domain. Each parameter of the Sines criterion will be calculated from the Power Spectral Densities of the stresses at each point of the structure. A finite element example is then used, at the end of this paper, to illustrate the application of the proposed strategy of calculation of the fatigue damage.