A case-based reasoning (CBR) system solves a new problem by retrieving\n`cases' that are similar to the given problem. If such a system can achieve\nhigh accuracy, it is appealing owing to its simplicity, interpretability, and\nscalability. In this paper, we demonstrate that such a system is achievable for\nreasoning in knowledge-bases (KBs). Our approach predicts attributes for an\nentity by gathering reasoning paths from similar entities in the KB. Our\nprobabilistic model estimates the likelihood that a path is effective at\nanswering a query about the given entity. The parameters of our model can be\nefficiently computed using simple path statistics and require no iterative\noptimization. Our model is non-parametric, growing dynamically as new entities\nand relations are added to the KB. On several benchmark datasets our approach\nsignificantly outperforms other rule learning approaches and performs\ncomparably to state-of-the-art embedding-based approaches. Furthermore, we\ndemonstrate the effectiveness of our model in an "open-world" setting where new\nentities arrive in an online fashion, significantly outperforming\nstate-of-the-art approaches and nearly matching the best offline method. Code\navailable at https://github.com/ameyagodbole/Prob-CBR\n