Decisions regarding classification problems in the healthcare domain can be particularly awkward since they involve a complex web of relevant uncertainties. In this respect, this paper proposes an evolutionary-fuzzy approach for facilitating the design of knowledge-based Decision Support Systems for classification problems. The approach is aimed at: i) introducing a set of design criteria to encode the medical knowledge elicited from clinical experts in terms of linguistic variables, linguistic values and fuzzy rules with the final aim of granting the interpretability; ii) defining a fuzzy inference technique to best fit the structure of medical knowledge and the peculiarities of the medical inference; iii) defining an evolutionary technique to tune the formalized knowledge by optimizing the shapes of the membership functions for each linguistic variable involved in the rules. The approach has been quantitatively evaluated on five medical databases commonly diffused in literature.