We report strong cosmological constraints on the Brans-Dicke (BD) theory of gravity using Cosmic Microwave Background data from Planck.We consider two types of models. First, the initial condition of the scalar field is fixed to give the same effective gravitational strength $G_{eff}$ today as the one measured on the Earth, $G_N$. In this case the BD parameter $\omega$ is constrained to $\omega > 692$ at the $99\%$ confidence level, an order of magnitude improvement over previous constraints.In the second type the initial condition for the scalar is a free parameter leading to a somewhat stronger constraint of $\omega > 890$ while $G_{eff}$ is constrained to $0.981 <\frac{G_{eff}}{G_N} <1.285$ at the same confidence level. We argue that these constraints have greater validity than for the BD theory and are valid for any Horndeski theory, the most general second-order scalar-tensor theory, which approximates BD on cosmological scales. In this sense, our constraints place strong limits on possible modifications of gravity that might explain cosmic acceleration.