In this paper, we propose a Foot-Instability-Based Adaptive (FIBA) covariance to dynamically adjust the covariance matrix for the pseudo-zero-velocity measurements in the Zero velocity UPdaTe (ZUPT)-aided Inertial Navigation Systems (INS). The proposed ZUPT-aided INS using the FIBA covariance is implemented in an Adaptive Extended Kalman Filter (AEKF) framework, where the measurement covariance matrix is updated in each iteration according to the FIBA covariance. The FIBA covariance is designed to have a very high value during the swing phases in a gait cycle, and the value significantly decreases during the stance phases. As a result, the proposed method eliminates a need to use a binary stance phase detector in implementation of the ZUPT-aided INS. Two series of indoor pedestrian navigation experiments were conducted to investigate the navigation performance of the algorithm. In the first series of experiments, which included cases of walking and running, localization solutions produced by the system using the FIBA covariance demonstrated 36% and 64% improvements in navigation accuracy along the horizontal and vertical directions, respectively. In the second series of experiments, which included a pedestrian walking on different indoor terrains, such as flat planes, stairs, and ramps, the navigation accuracy of the system using the FIBA covariance reduced horizontal and vertical position errors by 12% and 45%, respectively, as compared to the conventional ZUPT-aided INS.