  We construct uniform black-string solutions in Einstein-Gauss-Bonnet gravity
for all dimensions $d$ between five and ten and discuss their basic properties.
Closed form solutions are found by taking the Gauss-Bonnet term as a
perturbation from pure Einstein gravity. Nonperturbative solutions are
constructed by solving numerically the equations of the model. The
Gregory-Laflamme instability of the black strings is explored via linearized
perturbation theory. Our results indicate that new qualitative features occur
for $d=6$, in which case stable configurations exist for large enough values of
the Gauss-Bonnet coupling constant. For other dimensions, the black strings are
dynamically unstable and have also a negative specific heat. We argue that this
provides an explicit realization of the Gubser-Mitra conjecture, which links
local dynamical and thermodynamic stability. Nonuniform black strings in
Einstein-Gauss-Bonnet theory are also constructed in six spacetime dimensions.
