In this paper we present a parallel evolutionary multi-objective methodology for granularity and rule-based learning for Mamdani Fuzzy Systems. The proposed methodology produces a set of solutions with different trade-off between accuracy and interpretability, based on searching the number of labels and the fuzzy rules, and also makes a variable selection. This process is achieved by exploiting present parallel computer systems allowing it to deal with more complex models. ©2009 IEEE.