For a fluid layer heated and cooled differentially at its surface, we use a variational approach to place bounds on the viscous dissipation rate and a horizontal Nusselt measure based on the entropy production. With a general temperature distribution imposed at the top of the layer and a variety of thermal boundary conditions at the base of the layer, the horizontal Nusselt number is bounded by $cR_H^{1/3}$ as the horizontal Rayleigh number $R_H \,{\rightarrow}\, \infty$, for some constant $c.$ The analysis suggests that the ultimate regime for this so-called ‘horizontal convection’ is one in which the temperature field develops a boundary layer of width $O(R_H^{-1/3})$ at the surface, but has no variation in the interior. Although this scenario resonates with results of dimensional scaling theory and numerical computations, the bounds differ in the dependence of the Nusselt measure on $R_H$. Numerical solutions for steady convection appear to confirm Rossby's result that the horizontal Nusselt number scales like $R_H^{1/5}$, suggesting either that the bound is not tight or that the numerics have yet to reach the asymptotic regime.