We introduce a powerful and flexible MCMC algorithm for stochastic simulation. The method builds on a pseudo-marginal method originally introduced in [Genetics 164 (2003) 1139–1160], showing how algorithms which are approximations to an idealized marginal algorithm, can share the same marginal stationary distribution as the idealized method. Theoretical results are given describing the convergence properties of the proposed method, and simple numerical examples are given to illustrate the promising empirical characteristics of the technique. Interesting comparisons with a more obvious, but inexact, Monte Carlo approximation to the marginal algorithm, are also given.