In this paper, we suggest diagnosing InterOperability Testing problems by integrating Constraint-Based and Case-Based Reasoning. We model the problem as a Constraint Satisfaction Problem (CSP), then Case- Based Reasoning (CBR) is used to compensate for what is missing in this model. CBR supports the process of learning by supplying the case-base with new cases that can be used to solve future similar problems. CBR is also used to update the CSP model, and make it more robust for solving more problems. The domain we are using is InterOperability Testing of protocols in ATM (Asynchronous Transfer Mode) networks.