Recently, there has been an increased interest in the query reformulation using relevance feedback with evolutionary techniques such as genetic algorithm for multimedia information retrieval. However, these techniques have still not been exploited widely in the field of music retrieval. In this paper, we propose a novel music retrieval scheme that incorporates user relevance feedback with genetic algorithm to improve retrieval performance and develop a prototype system based on it. Our system also provides interesting easyto- use graphical user interfaces. For example, users can browse and play query results easily using markers in the music indicating those matched parts for the query. By performing various experiments, we show the effectiveness and efficiency of our proposed scheme.