Using inelastic neutron scattering, we show that the onset of superconductivity in underdoped Ba(Fe$_{1-x}$Co$_{x}$)$_{2}$As$_{2}$ coincides with a crossover from well-defined spin waves to overdamped and diffusive spin excitations. This crossover occurs despite the presence of long-range stripe antiferromagnetic order for samples in a compositional range from x=0.04-0.055, and is a consequence of the shrinking spin-density wave gap and a corresponding increase in the particle-hole (Landau) damping. The latter effect is captured by a simple itinerant model relating Co doping to changes in the hot spots of the Fermi surface. We argue that the overdamped spin fluctuations provide a pairing mechanism for superconductivity in these materials.