In recent years, we have witnessed an ever wider spread of multimedia streaming platforms (e.g., Netflix, Spotify, and Amazon). Hence, it has become more and more essential to provide such systems with advanced recommendation facilities, in order to support users in browsing these massive collections of multimedia data according to their preferences and needs. In this context, the modeling of entities and their complex relationships (e.g., users listening to topic-based songs or authors creating different releases of their lyrics) represents the key challenge to improve the recommendation and maximize the users' satisfaction. To this end, this is the first study to leverage the high representative power of hypergraph data structures in combination with modern graph machine learning techniques in the context of music recommendation. Specifically, we propose hypergraph embeddings for music recommendation (HEMR), a novel framework for song recommendation based on hypergraph embedding. The hypergraph data model allows us to represent seamlessly all the possible and complex interactions between users and songs with the related characteristics; meanwhile, embedding techniques provide a powerful way to infer the user-song similarities by vector mapping. We have experimented the effectiveness and efficiency of our approach with respect to the state-of-the-art most recent music recommender systems, exploiting the Million Song dataset. The results show that HEMR significantly outperforms other state-of-the-art techniques, especially in scenarios where the cold-start problem arises, thus making our system a suitable solution to embed within a music streaming platform.