•A multi-objective formulation on stability and tension is proposed for melody composition.•Music composition theories are employed in designing objective functions.•Music theory-guided genetic operators are developed with great care.•A multi-objective evolutionary framework is designed for automatic melody composition. Existing evolutionary approaches to automatic composition generate only a few melodies in a certain style that is specified by the setting of parameters or the design of fitness functions. Thus, their composition results cannot cover the various tastes of music. In addition, they are not able to deal with the multidimensional nature of music. This paper presents a novel multi-objective evolutionary approach to automatic melody composition in order to produce a variety of melodies at once. To this end, two conflicting fitness measures are investigated to evaluate the fitness of melody; (1) stability and (2) tension. Resorting to music theory, genetic operators (i.e., crossover and mutation) are newly designed to improve search capability in the multi-objective fitness space of music composition. The experimental results demonstrate the validity and effectiveness of the proposed approach. Moreover, the analysis of composition results proves that the proposed approach generates a set of pleasant and diverse melodies.