During the last years, multi-objective evolutionary algorithms (MOEAs) have been extensively used to generate fuzzy rule-based systems characterized by different trade-offs between accuracy and complexity. In this paper, we propose an MOEA-based approach to learn concurrently the rule and data bases of fuzzy rule-based classifiers (FRBCs). In particular, the rule bases are generated by exploiting a rule and condition selection (RCS) strategy, which selects a reduced number of rules from a heuristically generated set of candidate rules and a reduced number of conditions for each selected rule during the evolutionary process. RCS can be considered as a rule learning in a constrained search space. As regards the data base learning, the membership function parameters of each linguistic term used in the rules are learned concurrently to the application of RCS. We tested our approach on twenty-four classification benchmarks and compared our results with the ones obtained by two similar state-of-the-art MOEA-based approaches and by two well-known non-evolutionary classification algorithms, namely FURIA and C4.5. Using non-parametric statistical tests, we show that our approach generates FRBCs with accuracy and complexity statistically comparable to, and sometimes better than, the ones generated by the two MOEA-based approaches, exploiting, however, only the 5% of the number of fitness evaluations used by these approaches. Further, the classifiers generated by our approach result to be more interpretable than the ones generated by the FURIA and C4.5 algorithms, while achieving the same accuracy level.