Recommender systems are widely used for suggesting books, education materials, and products to users by exploring their behaviors. In reality, users’ preferences often change over time, which leads to the studies on time-dependent recommender systems. However, most existing approaches to deal with time information remain primitive. In this paper, we extend existing methods and propose a hidden semi-Markov model to track the change of users’ interests. Particularly, this model allows for users to stay in different (latent) interest states for different time periods, which is beneficial to model the heterogeneous length of users’ interest and focuses. We derive an EM algorithm to estimate the parameter of the framework, and predict users’ actions. Experiments on a real-world dataset show that our model significantly outperforms the state-of-the-art benchmark methods. Further analyses show that the performance depends on the allowed heterogeneity of latent states and the existence of user interest heterogeneity in the dataset.