The attempt to understand copper oxide superconductors is complicated by the presence of multiple strong interactions in these systems. Many believe that antiferromagnetism is important for superconductivity, but there has been renewed interest in the possible role of electron-lattice coupling1-4. The conventional superconductor MgB2has a very strong electron-lattice coupling, involving a particular vibrational mode (phonon) that was predicted by standard theory and confirmed quantitatively by experiment5. Here we present inelastic scattering measurements that show a similarly strong anomaly in the Cu-O bond-stretching phonon in the copper oxide superconductors La2−xSrxCuO4(withx = 0.07, 0.15). Conventional theory does not predict such behaviour. The anomaly is strongest in La1.875Ba0.125CuO4and La1.48Nd0.4Sr0.12CuO4, compounds that exhibit spatially modulated charge and magnetic order, often called stripe order6; it occurs at a wave vector corresponding to the charge order. These results suggest that this giant electron-phonon anomaly, which is absent in undoped and over-doped non-superconductors, is associated with charge inhomogeneity. It follows that electron-phonon coupling may be important to our understanding of superconductivity, although its contribution is likely to be indirect.