We consider a general Einstein–scalar–Gauss-Bonnet theory with a coupling function f (ϕ) between the scalar field and the quadratic gravitational Gauss-Bonnet term. We show that the existing no-hair theorems are easily evaded, and therefore black holes may emerge in the context of this theory. Indeed, we demonstrate that, under mild only assumptions for f (ϕ), asymptotic solutions describing either a regular black-hole horizon or an asymptotically-flat solution always emerge. We then show, through numerical integration, that the field equations allow for the smooth connection of these asymptotic solutions, and thus for the construction of a complete, regular black-hole solution with non-trivial scalar hair. We present and discuss the physical characteristics of a large number of such solutions for a plethora of coupling functions f (ϕ). Finally, we investigate whether pure scalar-Gauss-Bonnet black holes may arise in the context of our theory when the Ricci scalar may be altogether ignored.