We consider hairy black hole solutions of Einstein-Yang-Mills-dilaton theor
y, coupled to a Gauss-Bonnet curvature term, and we study their stability u
nder small, spacetime-dependent perturbations. We demonstrate that stringy
corrections do not remove the sphaleronic instabilities of colored black ho
les 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 limi
t of an infinitely large horizon, colored black holes are also found to be
unstable. Similar behavior is exhibited by magnetically charged black holes
while the bulk of neutral black holes are proved to be stable under small.
gauge-dependent perturbations. Finally, electrically charged black holes a
re found to be characterized only by the existence of a gravitational secto
r of perturbations. As in the case of neutral black holes, we demonstrate t
hat for the bulk of electrically charged black holes no unstable model, ari
se in this sector.