Wind speed estimation for rotary-wing vertical take-off and landing (VTOL) UAVs is challenging due to the low accuracy of airspeed sensors, which can be severely affected by the rotor’s down-wash effect. Unlike traditional aerodynamic modeling solutions, in this paper, we present a K Nearest Neighborhood learning-based method which does not require the details of the aerodynamic information. The proposed method includes two stages: an off-line training stage and an on-line wind estimation stage. Only flight data is used for the on-line estimation stage, without direct airspeed measurements. We use Parrot AR.Drone as the testing quadrotor, and a commercial fan is used to generate wind disturbance. Experimental results demonstrate the accuracy and robustness of the developed wind estimation algorithms under hovering conditions.