Multi-label classification problems exist in many real world applications where to each example in the dataset can be assigned a set of target labels. This paper presents a new two-step method for genetic learning of a fuzzy rule base for multi-label classification, called IRL-MLC. The first step uses a genetic algorithm based on an iterative approach to learn a preliminary rule base where the fitness of each rule depends on the degree of firing calculated for the set of labels of each example (positive or negatively) in the dataset. The second step uses a genetic algorithm to tune weights of each fuzzy rule in the preliminary rule base where the fitness of each set of weights is the precision of the multi-label classification. Experiments are conducted on five multi-label datasets, in biology, multimedia and text domains, and the proposed method has been compared with one state-of-art method. Results provide interesting insights into the quality of the discussed novel method.