We study two-dimensional Rayleigh-Bénard convection with Navier-slip, fixed temperature boundary conditions and establish bounds on the Nusselt number. As the slip-length varies with Rayleigh number Ra, this estimate interpolates between the Whitehead-Doering bound by Ra 5/12 for free-slip conditions (Whitehead & Doering. 2011 Ultimate state of two-dimensional Rayleigh-Bénard convection between free-slip fixed-temperature boundaries. Phys. Rev. Lett. 106, 244501) and the classical Doering-Constantin Ra 1/2 bound (Doering & Constantin. 1996 Variational bounds on energy dissipation in incompressible flows. III. Convection. Phys. Rev. E 53, 5957-5981). This article is part of the theme issue 'Mathematical problems in physical fluid dynamics (part 1)'.