Recommendation systems that automatically generate personalized music playlists for users have attracted tremendous attention in recent years. Nowadays, most music recommendation systems rely on item-based or user-based collaborative filtering or content-based approaches. In this paper, we propose a novel mixture hidden Markov model (HMM) for music play sequence prediction. We compare the mixture model with state-of-the-art methods and evaluate the predictions quantitatively and qualitatively on a large-scale real-world dataset in a Kaggle competition. Results show that our model significantly outperforms traditional methods as well as other competitors. We conclude by envisioning a next-generation music recommendation system that integrates our model with recent advances in deep learning, computer vision, and speech techniques, and has promising potential in both academia and industry.