  We consider hairy black hole solutions of Einstein-Yang-Mills-Dilaton theory,
coupled to a Gauss-Bonnet curvature term, and we study their stability under
small, spacetime-dependent perturbations. We demonstrate that the stringy
corrections do not remove the sphaleronic instabilities of the coloured black
holes with the number of unstable modes being equal to the number of nodes of
the background gauge function. In the gravitational sector, and in the limit of
an infinitely large horizon, the coloured black holes are also found to be
unstable. Similar behaviour is exhibited by the magnetically charged black
holes while the bulk of the neutral black holes are proven to be stable under
small, gauge-dependent perturbations. Finally, the electrically charged black
holes are found to be characterized only by the existence of a gravitational
sector of perturbations. As in the case of neutral black holes, we demonstrate
that for the bulk of electrically charged black holes no unstable modes arise
in this sector.
