The nonlinear Unified Strength Theory (UST), which takes into account the effect of intermediate stress and nonlinear behavior on geotechnical strength, is applied in slope stability analysis of earth-rockfill dams (ERD) in this paper. The biggest drawback for general determination of slip surface is that it must presuppose the shape of slip surface and is unable to identify the critical noncircular slip surface more accurately. This paper proposes an optimal analytic model of slope stability analysis of ERD and employs modified genetic algorithm (MGA) to search for the slip surface on the basis of shear failure criteria of the nonlinear UST without prior assumption of the shape of slip surface. The application of MGA dependent on Matlab toolbox to the slope stability analysis of ERD shows that MGA can consequently overcome the weakness of easily falling into local optimal solutions brought by general optimal algorithms.