  We obtain new vacuum static black hole solutions with anisotropic horizons in
Einstein-Gauss-Bonnet gravity with a negative cosmological constant in five
dimensions. The translational invariance along one direction on the
3-dimensional horizon cross section is broken. The Gauss-Bonnet coupling
{\alpha} is at the critical point where there is one single AdS vacuum. These
solutions does not appear in the form of a warped product, i.e. they lack a
common warping factor, and the metric contains 2 arbitrary functions, h(r) of
the radial coordinate r and H(y) of the horizon coordinate y -- some degeneracy
in the metric. The nontrivial horizon and the degeneracy may be closely related
to the critical value of {\alpha}. We introduce the process of obtaining the
solutions and some of their properties, and also prove a uniqueness theorem for
the case when there is a common warping factor for the rest two directions.
