This paper deals with the ergodicity (convergence of the marginals) and the law of large numbers for adaptive MCMC algorithms built from transition kernels that are not necessarily geometrically ergodic. We develop a number of results that significantly broaden the class of adaptive MCMC algorithms for which rigorous analysis is now possible. As an example, we give a detailed analysis of the adaptive Metropolis algorithm of Haario et al. [Bernoulli 7 (2001) 223–242] when the target distribution is subexponential in the tails.