Many emerging applications of space, ground, marine, and air vehicles require relative automated navigation with respect to other vehicles and objects. Disturbances in the environment may cause faults in relative navigation sensors. For sensors based on cameras or laser range finders, events as common as lighting changes, glint, or obstruction by debris could potentially cause spurious responses. Relative navigation is safety critical–fault tolerance must be addressed. We propose a fault detection, identification, and recovery architecture using multiple moving horizon estimators, each for a separate hypothesis of the fault state of the system. The hypothesis with maximum empirical likelihood is selected. Detected and identified faults are reported to the main navigation filter, which may then discard the relative navigation sensor data, and instead temporarily rely on the inertial navigation system. The guidance system may also act on the identified fault state, taking actions to recover the system to a safe state. This logic is demonstrated in simulation for the automated rendezvous and docking (AR&D) of spacecraft–a key technology for the near future demands of the space program. The simulation results demonstrate that faulty relative sensors may seriously affect the navigation solution. The proposed fault detection scheme has demonstrated an ability to identify faults in these sensors and take them offline before they disrupt navigation and lead to mission failure.