In vision-aided navigation, several challenges affect algorithm performance in different ways. These challenges include terrain type, sensor technology, cloud coverage, sensor malfunction, and environmental conditions such as illumination. Currently, ordinance such as precision-guided munitions, may experience any of these challenges over the course of the mission. Each challenge has an associated probability-of-occurrence, e.g. probability that clouds will obscure the field-of-view, or that sensor hardware will induce image blurring or other artifacts that impede scene imaging ability. Different navigation algorithms respond differently to each challenge. By capturing these outcomes for a given algorithm and understanding the likelihood that such challenges occur during a mission, we can derive the overall mission-reliability and performance ranking of that algorithm. In this context, reliability refers to the ability of an algorithm to maintain a required Circle of Equal Probability at the target location that ensures mission success. Moreover, in multi-vendor system development efforts, critical algorithms such as navigation are frequently provided as a proprietary “black-box,” with no visibility into internal functioning. The absence of internal visibility makes performance evaluation more challenging. In this paper we present our novel analysis approach, and results from application to a black-box state-of-the-art navigation algorithm developed for navigation in GPS-denied environments. Our approach identifies possible technologies used, and delineates hypothesized challenges affecting algorithm performance. It identifies all algorithm inputs and develops an evaluation framework where all challenges can be applied individually and successively to evaluate mission worthiness, i.e., mission reliability. Challenges refer to realistic, confounding stressors, arising in-mission, such as terrain type differences, attitude errors, imager faults, cloud coverage, and timing errors.