This paper presents an efficient approach for predicting high-cycle fatigue crack initiation life under general multiaxial fatigue loadings. A minimum circumscribed ellipse approach is proposed for evaluating the effective shear stress amplitude and mean value throughout a complex loading cycle. The idea of this approach is to construct a minimum circumscribed ellipse enclosing the loading path in the transformed deviatoric stress space. The new definition of the effective shear stress amplitude is the root mean square of the major semi-axis and the minor semi-axis of the minimum circumscribed ellipse. In this way, the out-of-phase loading effects are taken into account and improvement is made over the previous approaches such as the longest projection, the longest chord, and the minimum circumscribed circle methods. By using mathematical programming techniques, an efficient numerical algorithm is proposed for solving the min-max problem of finding the minimum circumscribed ellipse that can enclose the whole loading path. This new approach allows extension of the Sines or Crossland fatigue criteria to fatigue life prediction under general multiaxial loading with arbitrary stress-time histories. Multiaxial fatigue test results collected from literature, which include complex stress histories with different waveforms, frequencies, out-of-phase angles and mean stresses, were used to validate the approach here proposed.