Design of optimal controllers satisfying performance criteria of minimum tracking error and disturbance level for an interval system using a multi-objective evolutionary approach is proposed in this paper. Based on a worst-case design philosophy, the design problem is formulated as a minimax optimization problem, subsequently solved by a proposed two-phase multi-objective genetic algorithm (MOGA). By using two sets of interactive genetic algorithms where the first one determines the maximum (worst-case) cost function values for a given set of controller parameters while the other one minimizes the maximum cost function values passed from the first genetic algorithm, the proposed approach evolutionarily derives the optimal controllers for the interval system. To suitably assess chromosomes for their fitness in a population, root locations of the 32 generalized Kharitonov polynomials will be used to establish a constraints handling mechanism, based on which a fitness function can be constructed for effective evaluation of the chromosomes. Because of the time-consuming process that genetic algorithms generally exhibit, particularly the problem nature of minimax optimization, a parallel computation scheme for the evolutionary approach in the MATLAB-based working environment is also proposed to accelerate the design process.