This paper introduces an Evolutionary Programming algorithm for solving classification problems using highly interpretable IF-THEN classification rules. It is an algorithm aimed to maximize the comprehensibility of the classifier by minimizing the number of rules and employing only relevant attributes. The proposal is evaluated and compared to other 5 well-known classification techniques over 18 datasets. The results obtained from the experiments show its competitive accuracy and the significantly better interpretability of the classifiers provided in terms of number of rules, number of conditions and a complexity metric.