A new model is proposed to automatically classify sleep stages using heart rate variability (HRV). The generative model, based on the characteristics that the distribution and the transition probabilities of sleep stages depend on the elapsed time from the beginning of sleep, infers the sleep stage with a Gibbs sampler. Experiments were conducted using a public data set consisting of 45 healthy subjects and the model\'s classification accuracy was evaluated for three sleep stages: wake state, rapid eye movement (REM) sleep, and non-REM sleep. Experimental results demonstrated that the model provides more accurate sleep stage classification than conventional (naive Bayes and Support Vector Machine) models that do not take the above characteristics into account. Our study contributes to improve the quality of sleep monitoring in the daily life using easy-to-wear HRV sensors.