Computing the partition function of a graphical model is a fundamental task in probabilistic inference. Variational bounds and Monte Carlo methods, two important approxi- mate paradigms for this task, each has its respective strengths for solving different types of problems, but it is often non- trivial to decide which one to apply to a particular problem instance without significant prior knowledge and a high level of expertise. In this paper, we propose a general framework that interleaves optimization of variational bounds (via mes- sage passing) with Monte Carlo sampling. Our adaptive inter- leaving policy can automatically balance the computational effort between these two schemes in an instance-dependent way, which provides our framework with the strengths of both schemes, leads to tighter anytime bounds and an unbiased estimate of the partition function, and allows flexible trade- offs between memory, time, and solution quality. We verify our approach empirically on real-world problems taken from recent UAI inference competitions.