Kohn-Sham density functional theory is the workhorse computational method in materials and surface science(1). Unfortunately, most semilocal density functionals predict surfaces to be more stable than they are experimentally. Naively, we would expect that consequently adsorpion energies on surfaces are too small as well, but the contrary is often found: chemisorption energies are usually overestimated(2). Modifying the functional improves either the adsorption energy or the surface energy but always worsens the other aspect. This suggests that semilocal density functionals possess a fundamental flaw that is difficult to cure, and alternative methods are urgently needed. Here we show that a computationally fairly efficient many-electron approach, the random phase approximation(3) to the correlation energy, resolves this dilemma and yields at the same time excellent lattice constants, surface energies and adsorption energies for carbon monoxide and benzene on transition-metal surfaces.