At the dawn of a new era of intelligent applications in the music sector, the automatic genre-based classification of music tracks is a paramount task for the development of different services, such as music recommenders. In that sense, current solutions to uncover the genre of a song usually follow a multi-class approach revealing only a single genre per target song. However, songs do not usually belong to a single music genre but a mixture of them. In this context, the present work introduces SINATRA, a novel multi-label classifier of music genres of songs. By following an iterative procedure that continuously reduces the dimensional space of the genres, SINATRA is able to tag a song with multiple and complementary genres. The aforementioned dimensionality reduction is done by computing a graph comprising the co-occurrences of genres in songs. The evaluation results shows that SINATRA achieve an accuracy score above 0.5 given genre space covering more than 2,000 music genres.