A novel Adaptive Fractional-Order Proportional-Integral-Derivative (AFOPID) control is designed to realize the Maximum Power Point Tracking (MPPT) of a Permanent Magnet Synchronous Generator (PMSG). First, the generator nonlinearities, parameter uncertainties, unmodelled dynamics, stochastic wind speed are all aggregated into a perturbation, which is estimated online by a High-Gain State And Perturbation Observer (HGSPO). Then, the Fractional-Order Proportional-Integral-Derivative (FOPID) control is employed to fully compensate for the perturbation estimate, such that a globally consistent robust control performance under various operation conditions can be achieved. AFOPID control has a better MPPT performance than PID control. It does not require an accurate PMSG model while only the measurement of d-axis current and mechanical rotation speed is needed. Two cases are carried out i.e. step change of wind speed and stochastic wind variation. Simulation results validate the effectiveness and robustness of AFOPID control compared to that of PID control, FOPID control and Feedback Linearization Control (FLC). This work is supported by National Natural Science Foundation of China (No. 51777078 and No. 61963020), Yunnan Power Grid Stability Control Technology Research and Closed Loop Simulation Platform with Multiple DC and High Proportion of New Energy (No. KJDK2018210), and the Applied Basic Research Projects of Yunnan (No. 2018FD036).