A new algorithm for training Restricted Boltzmann Machines is introduced. The algorithm, named Persistent Contrastive Divergence, is different from the standard Contrastive Divergence algorithms in that it aims to draw samples from almost exactly the model distribution. It is compared to some standard Contrastive Divergence algorithms on the tasks of modeling handwritten digits and classifying digit images by learning a model of the joint distribution of images and labels. The Persistent Contrastive Divergence algorithm outperforms other Contrastive Divergence algorithms, and is equally fast and simple.