Simulating electron spin resonance (ESR) spectra directly from molecular dynamics simulations of a spinlabeled protein necessitates a large number (hundreds or thousands) of relatively long (hundreds of nanoseconds) trajectories. To meet this challenge, we explore the possibility of constructing accurate stochastic models of the spin label dynamics from atomistic trajectories. A systematic, two-step procedure, based on the probabilistic framework of hidden Markov models, is developed to build a discrete-time Markov chain process that faithfully captures the internal spin label dynamics on time scales longer than about 150 ps. The constructed Markov model is used both to gain insight into the long-lived conformations of the spin label and to generate the stochastic trajectories required for the simulation of ESR spectra. The methodology is illustrated with an application to the case of a spin-labeled poly alanine (x helix in explicit solvent.