Damage prognosis of high-speed blades is very important for industrial turbomachinery. Nowadays, vibration monitoring using blade tip-timing methods is becoming promising. However, its main drawback is blade tip-timing signals are subsampled. Very few works have been done on damage prognosis using subsampled blade tip-timing signals. This paper investigates a novel method of blade damage prognosis based on kernel principal component analysis and grey model. Firstly, a nonaliasing reconstruction algorithm of subsampled blade tip-timing signals is proposed based on the Shannon theorem and wavelet packet transform. Secondly, kernel principal component analysis is done on the damage feature space and a damage index is defined by Mahalanobis distance. Then a grey model (1) model is proposed for damage prognosis. In the end, an experimental setup is built and a long time testing is done for collecting samples. The experimental results validate the superiority of the proposed method.