In this paper we study the hyperbolicity of the equations of motion for the most general Horndeski theory of gravity in a generic "weak field" background. We first show that a special case of this theory, namely Einstein-dilaton-Gauss-Bonnet gravity, fails to be strongly hyperbolic in any generalised harmonic gauge. We then complete the proof that the most general Horndeski theory which, for weak fields, is strongly hyperbolic in a generalised harmonic gauge is simply a "k-essence" theory coupled to Einstein gravity and that adding any more general Horndeski term will result in a weakly, but not strongly, hyperbolic theory.