Degradation prognostics of aero-engine are a well-recognized challenging issue. Data-driven prognostic techniques have been receiving attention because they rely on neither expert knowledge nor mathematic model of the system. But they are highly dependent on the quantity and quality of degradation data. To solve the problems caused by unlabeled, unbalanced condition monitoring (CM) data and uncertainties of the prognostics process, a novel data-driven aero-engine degradation prognostic strategy is proposed in this article. First, two indicators are defined to remove redundant degradation features. Then, the number of discrete states of health is determined by a fuzzy c -means algorithm, and the health state labels can be automatically assigned for health state estimation, where the uncertain initial condition and the uncertainty of health state's transition are fully considered. Finally, a multivariate health estimation model and a multivariate multistep-ahead long-term degradation prediction model are proposed for remaining useful life estimation for aero-engines. Verification results using the aero-engine data from NASA can show that the proposed data-driven degradation prognostic strategy is effective and feasible.