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.