We present observations of a major outburst at centimeter, millimeter, optical, X-ray, and gamma-ray wavelengths of the BL Lacertae object AO 0235+164 in 2008. We analyze the timing of multi-waveband variations in the flux and linear polarization, as well as changes in Very Long Baseline Array (VLBA) images at 7mm with ~0.15 milliarcsecond resolution. The association of the events at different wavebands is confirmed at high statistical significance by probability arguments and Monte-Carlo simulations. A series of sharp peaks in optical linear polarization, as well as a pronounced maximum in the 7mm polarization of a superluminal jet knot, indicate rapid fluctuations in the degree of ordering of the magnetic field. These results lead us to conclude that the outburst occurred in the jet both in the quasi-stationary core and in the superluminal knot, both at >12 parsecs downstream of the supermassive black hole. We interpret the outburst as a consequence of the propagation of a disturbance, elongated along the line of sight by light-travel time delays, that passes through a standing recollimation shock in the core and propagates down the jet to create the superluminal knot. The multi-wavelength light curves vary together on long time-scales (months/years), but the correspondence is poorer on shorter time-scales. This, as well as the variability of the polarization and the dual location of the outburst, agrees with the expectations of a multi-zone emission model in which turbulence plays a major role in modulating the synchrotron and inverse Compton fluxes.