In some cases, such as restarting after power interruption or starting a motor rotated by external load, the motor may be rotating before being powered by the inverter. For speed-sensorless operation, as both the initial rotational direction and speed is unknown, it would be difficult to achieve smooth and fast resumption of normal operation if the starting scheme is not deliberately designed. In this paper, a method based on adaptive full order observer (AFO) is proposed to address this problem. For AFO without a properly designed feedback gain matrix, the estimated speed cannot converge to the actual speed if initial estimated speed is significantly lower than the actual speed. Through analyzing the transfer function of stator current error, the convergence condition of speed estimation is deduced. A feedback gain matrix and the condition for shifting to normal operation are subsequently proposed to improve restarting performance. The detailed design and implementation of the proposed method combined with finite control set model-predictive flux control is illustrated. Simulation and experimental results validate the effectiveness of the developed schemes.