Seismic facies classification aims to predict a facies model, or a set of facies models, from measured seismic data. We focus on stochastic classification methods to estimate the probability distribution of facies conditioned on seismic data. Bayesian classification methods based on analytical solutions are generally applied to seismically inverted elastic attributes or petrophysical properties rather than measured seismic data, and they do not include spatial correlation models in the prior distribution. Instead, iterative stochastic methods, such as Monte Carlo acceptance-rejection sampling and approximate Bayesian computation, can be directly applied to seismic data and can be implemented with complex prior models; however, their convergence is generally slow because it requires the simulation of a large number of facies models from the prior distribution. We develop an efficient implementation of a Markov chain Monte Carlo (MCMC) approach that adopts complex prior models, such as multiple-point statistics simulations based on a training image, to generate geologically realistic facies realizations. The novelty of the approach is that the proposal distribution of the proposed MCMC method is based on a gradual deformation algorithm, in which the proposal distribution is expressed as a linear combination of the indicator variables of the previously accepted model and a random prior simulation, according to a uniform random weight. The synthetic examples indicate accurate facies predictions with a success rate of approximately 80% for well-log facies classification based on elastic attributes and approximately 60% for seismic facies classification based on seismic data. The inversion is compared to an MCMC method with prior models sampled from a first-order Markov chain and Bayesian facies classification.