During the starting process of aero-engine starter motor, the load characteristics change with the speed. At the same time, the difference of starting environment and the change of motor parameters bring difficulties to the start-up control. In order to overcome the shortcomings of traditional control strategies in dealing with these uncertainties, a fractional order active disturbance rejection controller based on random evolution grey wolf optimization (REGWO-FO-ADRC) is proposed. Through the active disturbance rejection control (ADRC), anti-disturbance capability of the system in the starting process is enhanced. The fractional order (FO) control is adopted to suppress the observer estimation error caused by the upper limit of bandwidth and ensure the control quality. The random evolution grey wolf optimization (REGWO) algorithm is designed to realize online self-adaption of the control parameters of the FO controller. The variable evolutionary rate is used to describe the update process of population, which enriches the randomness and improves the global search ability and convergence speed. Simulation results show that the designed controller can effectively suppress the influence of many uncertainties on the system and improve the starting performance of aero-engine.