The adsorption of aromatic molecules on metal surfaces plays a key role in condensed matter physics and functional materials. Depending on the strength of the interaction between the molecule and the surface, the binding is typically classified as either physisorption or chemisorption. Van der Waals (vdW) interactions contribute significantly to the binding in physisorbed systems, but the role of the vdW energy in chemisorbed systems remains unclear. Here we study the interaction of benzene with the (111) surface of transition metals, ranging from weak adsorption (Ag and Au) to strong adsorption (Pt, Pd, Ir, and Rh). When vdW interactions are accurately accounted for, the barrier to adsorption predicted by standard density functional theory (DFT) calculations essentially vanishes, producing a metastable precursor state on Pt and Ir surfaces. Notably, vdW forces contribute more to the binding of covalently bonded benzene than they do when benzene is physisorbed. Comparison to experimental data demonstrates that some of the recently developed methods for including vdW interactions in DFT allow quantitative treatment of both weakly and strongly adsorbed aromatic molecules on metal surfaces, extending the already excellent performance found for gas-phase molecules.