Here we shall show that there is no other instability for the Einstein-Gauss-Bonnet-anti-de Sitter (AdS) black holes, than the eikonal one and consider the features of the quasinormal spectrum in the stability sector in detail. The obtained quasinormal spectrum consists from the two essentially different types of modes: perturbative and non-perturbative in the Gauss-Bonnet coupling alpha. The sound and hydrodynamic modes of the perturbative branch can be expressed through their Schwazrschild-AdS limits by adding a linear in alpha correction to the damping rates: omega approximate to Re omega_(SAdS) - Im omega_(SAdS) (1 - alpha ((D + 1)(D - 4)/2R^(2)))i, where R is the AdS radius. The non-perturbative branch of modes consists of purely imaginary modes, whose damping rates unboundedly increase when alpha goes to zero. When the black hole radius is much larger than the anti-de Sitter radius R, the regime of the black hole with planar horizon (black brane) is reproduced. If the Gauss-Bonnet coupling alpha (or used in holography lambda_(GB)) is not small enough, then the black holes and branes suffer from the instability, so that the holographic interpretation of perturbation of such black holes becomes questionable, as, for example, the claimed viscosity bound violation in the higher derivative gravity. For example, D = 5 black brane is unstable at vertical bar lambda_(GB)vertical bar > 1/8 and has anomalously large relaxation time when approaching the threshold of instability.