We consider the problem of predicting users’ preferences on online platforms. We build on recent findings suggesting that users’ preferences change over time, and that helping users expand their horizons is important in ensuring that they stay engaged. Most existing models of user preferences attempt to capture simultaneous preferences: “Users who like A tend to like B as well”. In this paper, we argue that these models fail to anticipate changing preferences. To overcome this issue, we seek to understand the structure that underlies the evolution of user preferences. To this end, we propose the Preference Transition Model (PTM), a dynamic model for user preferences towards classes of items. The model enables the estimation of transition probabilities between classes of items over time, which can be used to estimate how users’ tastes are expected to evolve based on their past history. We test our model’s predictive performance on a number of different prediction tasks on data from three different domains: music streaming, restaurant recommendations and movie recommendations, and find that it outperforms competing approaches. We then focus on a music application, and inspect the structure learned by our model. We find that the PTM uncovers remarkable regularities in users’ preference trajectories over time. We believe that these findings could inform a new generation of dynamic, diversity-enhancing recommender systems.