Self-healing, one of the four key properties characterizing Autonomic Systems, can enable large-scale software systems delivering complex services on a 24/7 basis to meet their goals without requiring any human intervention. In this paper we present a self-healing methodology for software systems based on Case-Based Reasoning, a reasoning paradigm that exploits the unformalized knowledge embedded into already solved instances of problems, able to take advantage from the fact that in software systems most errors are just re-occurrences of known problems. We demonstrate the practical applicability of our methodology by showing how it can be used to obtain a self-healing software system delivering large-scale Internet services.