In this paper, a residual-based fault detection and exclusion (FDE) algorithm is developed to enhance the performance of the tightly coupled Global Navigation Satellite System (GNSS) and Inertial Navigation System (INS) system. Specifically, Rényi divergence (RD) and its modification are introduced as the measure to evaluate the distance/divergence between the state estimate of propagation and update steps to indicate whether there exists a fault in the system. The properties of this indicator mechanism are discussed analytically in detail. An FDE algorithm is constructed based on this divergence measure. Appropriate methods to select the parameters of the proposed divergence measure to increase the probability of the fault detection and decrease the false alarm rate of the FDE algorithm are proposed. The results are demonstrated and validated in the Computer Aided Design of Aerospace Concepts (CADAC++) flight simulation platform.