Let P(E) be the space of probability measures on a measurable space (E, ε). In this paper we introduce a class of nonlinear Markov chain Monte Carlo (MCMC) methods for simulating from a probability measure π ∈ P(E). Nonlinear Markov kernels (see [Feynman-Kac Formulae: Genealogical and Interacting Particle Systems with Applications (2004) Springer]) K: P(E) × E → P(E) can be constructed to, in some sense, improve over MCMC methods. However, such nonlinear kernels cannot be simulated exactly, so approximations of the nonlinear kernels are constructed using auxiliary or potentially self-interacting chains. Several nonlinear kernels are presented and it is demonstrated that, under some conditions, the associated approximations exhibit a strong law of large numbers; our proof technique is via the Poisson equation and Foster-Lyapunov conditions. We investigate the performance of our approximations with some simulations. © 2011 ISI/BS.