Recently it has been argued that in Einstein gravity anti-de Sitter spacetime is unstable against the formation of black holes for a large class of arbitrarily small perturbations. We examine the effects of including a Gauss-Bonnet term. In five dimensions, spherically symmetric Einstein-Gauss-Bonnet gravity has two key features: Choptuik scaling exhibits a radius gap, and the mass function goes to a finite value as the horizon radius vanishes. These suggest that black holes will not form dynamically if the total mass-energy content of the spacetime is too small, thereby restoring the stability of anti-de Sitter spacetime in this context. We support this claim with numerical simulations and uncover a rich structure in horizon radii and formation times as a function of perturbation amplitude.