This talk will present a novel algorithm for early detection of aeroelastic flutter when onset conditions are approached during flutter tests of flight vehicles. The approached stability boundary is detected by identifying substantial regularity increase of the structural vibrations. Two new regularity features are presented and examined along with existing regularity features used in previous work. The flutter early warning is accomplished using measured signals only, in response to clear-air turbulence, and with essentially no prior knowledge needed about the aircraft or the flutter mechanism involved. The algorithm consists of three stages: (1) extraction of regularity features, (2) calibration by addition of white noise to nominal measurements, and (3) thresholding. Four types of datasets were used: (a) synthetic data, (b) simulated data generated using aeroelastic response simulations to stochastic gusts, (c) measured data from a flutter wind tunnel experiment, and (d) data recorded in a previously performed flight test with several non-distructive flutter events. Feature selection and evaluation was performed on synthetic data and validated on measured signals. Threshold values were obtained from wind tunnel data and were shown to be applicable for flight test data. The algorithm was shown to be able to flag an impending flutter event before critical onset occurs for the A3TB UAV flight test sensor measurements.