Modeling the effect of multi-axial mechanical stress on the iron losses of an M400-50A grade non-oriented electrical steel sheet is studied. By utilizing the statistical loss theory, the total measured iron losses are first segregated to hysteresis, classical eddy current and excess losses. Then, the stress dependency of the excess losses is modeled by correlating them to the hysteresis losses under multi-axial stress. This correlation, coupled with a magneto-elastic invariant based loss model, can be used to predict the iron loss evolution with reasonable accuracy under multi-axial stress when only iron loss data under no applied stress at various excitation frequencies and under only two uniaxial stress levels at quasi-static excitation are available. Consequently, this approach significantly reduces the required measurement data for estimating the iron losses under multi-axial stress.