This paper introduces a novel Prognostics-enhanced Automated Contingency Management (or ACM+P) paradigm based on both current health state (diagnosis) and future health state estimates (prognosis) for advanced autonomous systems. Including prognostics in ACM system allows not only fault accommodation, but also fault mitigation via proper control actions based on short term prognosis, and moreover, the establishment of a long term operational plan that optimizes the utility of the entire system based on long term prognostics. Technical challenges are identified and addressed by a hierarchical ACM+P architecture that allows fault accommodation and mitigation at various levels in the system ranging from component level control reconfiguration, system level control reconfiguration, to high level mission re-planning and resource redistribution. The ACM+P paradigm was developed and evaluated in a high fidelity Unmanned Aerial Vehicle (UAV) simulation environment with flight-proven baseline flight controller and simulated diagnostics and prognostics of flight control actuators. Simulation results are presented. The ACM+P concept, architecture and the generic methodologies presented in this paper are applicable to many advanced autonomous systems such as deep space probes, unmanned autonomous vehicles, and military and commercial aircraft.