Power system health prognosis is a key process of condition-based maintenance. For the problem of large error in the residual lifetime prognosis of a power system, a novel residual lifetime prognosis model based on a high-order hidden semi-Markov model (HOHSMM) is proposed. First, HOHSMM is developed based on the hidden semi-Markov model (HSMM). An order reduction method and a composite node mechanism of HOHSMM based on permutation are proposed. The health state transition matrix and observation matrix are improved accordingly. The high-order model is transformed into the corresponding first-order model, and more node dependency information is stored in the parameter group to be estimated. Secondly, in order to estimate the parameters and optimize the structure of the proposed model, an intelligent optimization algorithm group is used instead of the expectation−maximization (EM) algorithm. Thus, the simplification of the topology of the high-order model by the intelligent optimization algorithm can be realized. Then, the state duration variables in the high-order model are defined and deduced. The prognosis method based on polynomial fitting is used to predict the residual lifetime of the power system when the prior distribution is unknown. Finally, the intelligent optimization algorithm is used to solve the proposed model, and experiments are performed based on a set of power system data sets to evaluate the performance of the proposed model. Compared with HSMM, the proposed model has better performance on the power system health prognosis problem and can get a relatively good solution in a short computation time.