This paper investigates the efficiency of Harmony Search based algorithms for solving multi-objetive problems. For this task, four variants of the Harmony Search algorithm were adapted in the Non-dominated Sorting Genetic Algorithm II (NSGA-II) framework. Harmony Search is a recent proposed music-inspired metaheuristic while NSGA-II is a very successful evolutionary multi-objective algorithm. The four proposed methods are tested against each other using a set of benchmark instances proposed in CEC 2009. The best proposed algorithm is also compared with NSGA-II. The preliminary results are very promising and stand the proposed approach as a candidate to the State-of-the-art for multi-objective optimization, encouraging further researches in the hybridization of the Harmony Search and Multi-objective Evolutionary Algorithms.