We report the existence of unstable s-wave modes for black strings in Gauss-Bonnet theory (which is quadratic in the curvature) in seven dimensions. This theory admits analytic uniform black strings that are, in the transverse section, black holes of the same Gauss-Bonnet theory in six dimensions. All the components of the perturbation can be written in terms of a single component and its derivatives. For this, we find a master equation that admits bounded solutions provided the characteristic time of the exponential growth of the perturbation is related to the wave number along the extra direction, as in general relativity. It is known that these configurations suffer from a thermal instability; therefore, the results presented here provide evidence for the Gubser-Mitra conjecture in the context of Gauss-Bonnet theory. Because of the nontriviality of the curvature of the background, all of the components of the metric perturbation appear in the linearized equations. Similar to spherical black holes, the black strings should be obtained as the short-distance limit r << alpha(1/2) of the black-string solution of Einstein-Gauss-Bonnet theory (which is not known analytically), where alpha is the Gauss-Bonnet coupling.