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 beyond the narrow set of their current preferences 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 estimating probabilities of transitions 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 recommendation, 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 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.