Gravitational perturbations of higher-dimensional black holes in the Einstein-Gauss-Bonnet theory, proposed by Boulware and Deser, have been extensively studied in numerous works, primarily focusing on the fundamental mode. These studies have shown that for sufficiently small black holes, comparing to the Gauss-Bonnet coupling parameter, a dynamical instability arises. In this work, for the first time, we conduct a comprehensive analysis of the behavior of overtones. We demonstrate that while the fundamental mode remains largely unchanged due to the limited stability region, the first few overtones deviate from their Tangherlini limits at an increasing rate. This deviation reflects the impact of the coupling parameter on the near-horizon structure of the black hole.