Medical diagnosis and prognosis is an emblematic example for classification problems. Machine learning could provide invaluable support for automatically inferring diagnostic rules from descriptions of past cases, making the diagnosis process more objective and reliable. Since the problem involves both test and misclassification costs, we have analyzed ICET, the most prominent approach in the literature for complex cost problems. The hybrid algorithm tries to avoid the pitfalls of traditional greedy induction by performing a heuristic search in the space of possible decision trees through evolutionary mechanisms. Our implementation solves some of the problems of the initial ICET algorithm, proving it to be a viable solution for the problem considered.