In a vision-aided autonomous system, it is crucial to have a consistent covariance matrix of the navigation solution. Overconfidence in covariance could lead to significant deviation of the navigation solution and failures of autonomous missions, especially in a global positioning system-denied environment. Consistency of a map-based vision-aided navigation system is investigated in this paper. As has been shown in numerous previous works, the traditional extended Kalman filter (EKF) approach to navigation produces significantly inconsistent (overconfident) covariance estimates. Covariance intersection and adjusted EKF approaches can both help to resolve the overconfidence problem. We present both simulation-based and real-world results of each of these approaches and investigate the consistency of their solutions.