Stall and upset situations occurring on airborne vehicles exhibit a substantially dangerous behaviour in terms of safety. If the aircraft is not successfully recovered from the upset condition, the consequences are often fatal. In recent years, there have been a considerable effort for designing feedback control systems for autonomous recovery from stall and upset conditions. In this paper, we present a novel finite state automaton structure coupled with a switching nonlinear control system that enables autonomous recovery from a large set of initial conditions. The states of the automaton and transition conditions are designed based on Federal Aviation Administration’s guidelines for upset recovery. The overall design is demonstrated on a 6 degrees of freedom nonlinear F-16 model by analyzing the autonomous recovery performance for various initial pitch/roll angles. It is shown that the developed methodology successfully recovers the aircraft for a large portion of the considered scenarios.