Malaria is life threatening disease in Ethiopia specifically in Tigray region. Having common symptoms with other diseases makes it complex and challenging to diagnose effectively. In this paper case based reasoning framework for malaria diagnosis has been designed to diminish the challenges faced by inexperienced practitioners during malaria diagnosis and to solve the problem on shortage of health professionals. The required knowledge for this study was collected through interview and document analysis from domain experts, malaria patient history cards and other related relevant documents. In the case acquisition process the manual format of cases makes the process too challenging. Decision tree is used to model the acquired knowledge. The case structure was then constructed using the selected most determinant attributes. Machine learning approach is applied to select the most relevant features. Feature-vector case representation technique is applied to represent the collected malaria cases. Jcolibri programming tool integrated with Eclipse and Nearest Neighbor retrieval algorithm are used to design the framework. To the end based on the results we can say that the machine learning approach can be used to select most relevant attributes in diseases having several common symptoms and designing case-based diagnosis frameworks could overcome the main problems observed in health centers of Tigray. As an artifact the framework is evaluated by statistical analysis, comparative evaluation, user evaluation and other evaluation techniques. Averagely 79 % precision, 89 % recall, 91.4% accuracy and 78.8% domain expert’s evaluation was the results scored.