In this paper, a novel adaptive Fault-Tolerant Control (FTC) strategy is proposed for non-minimum phase Hypersonic Vehicles (HSVs) that are affected by actuator faults and parameter uncertainties. The strategy is based on the output redefinition method and Adaptive Dynamic Programming (ADP). The intelligent FTC scheme consists of two main parts: a basic fault-tolerant and stable controller and an ADP-based supplementary controller. In the basic FTC part, an output redefinition approach is designed to make zero-dynamics stable with respect to the new output. Then, Ideal Internal Dynamic (IID) is obtained using an optimal bounded inversion approach, and a tracking controller is designed for the new output to realize output tracking of the non-minimum phase HSV system. For the ADP-based compensation control part, an Action-Dependent Heuristic Dynamic Programming (ADHDP) adopting an actor-critic learning structure is utilized to further optimize the tracking performance of the HSV control system. Finally, simulation results are provided to verify the effectiveness and efficiency of the proposed FTC algorithm.