Case-Based Reasoning relies on the underlying hypothesis that similar problems have similar solutions. The extent to which this hypothesis holds good has been used by CBR designers as a measure of case base complexity, which in turn gives insights on its generalization ability. Several local and global complexity measures have been proposed in the literature. However, the existing measures rely only on the similarity knowledge to compute complexity. We propose a new complexity measure called Reachability-Based Complexity Measure (RBCM) that goes beyond the similarity knowledge to include the effects of all knowledge containers in the reasoner. The proposed measure is evaluated on several realworld datasets and results suggest that RBCM correlates well with the generalization accuracy of the reasoner. © 2019, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.