Condition-based maintenance (CBM) can be broadly applied to aero-engine prognostic and health management (PHM) in order to economize the cost of repair and to improve the systems efficiency. PHM process of aero-engine usually requires prediction for rest useful life (RUL) and health indicator (HI) as feedback information for CBM. In general, aero-engine PHM algorithm predicts RUL and HI values based on historical aero-engine work record. Former PHM methods which demand all historical data to estimate RUL lead to a credible estimation but at the same time result in increment of cost and inconvenience of PHM process. To provide more flexible and lower requirements for data maintenance PHM approachs, this paper proposes a deep learning (DL) algorithm to predict RUL and HI based on only one flight cycles working record. The designed DL algorithm is named recurrent neural network based feature extraction non-linear regression algorithm (RNNFE-NLRA), which combines a recurrent neural network to extract deep features from working record during one flight, a feedforward neural network to be a non-linear regression for estimating RUL and HI, a Kalman filter to rectify the predicted result. A newly published data set including 35 aero-engine samples is used to verify the applicability of the algorithm proposed. We also evaluate the designed model against other related works. The results show that the designed algorithm estimates an RUL with the same accuracy for different stages of aero-engine degradation process while former PHM approaches estimate with difference. A stable accuracy for all stages of degradation returns more generalization ability. Furthermore, by using only one flight information, our algorithm can reduce the models complexity and economize data maintenance cost and can operate in a more flexible and efficient way than former works. Due to the advantages above, the designed algorithm can not only be used in aero-engine PHM but also in a similar complex engineering systems PHM case.