We study thermodynamic properties and phase structures of topological black holes in Einstein theory with a Gauss-Bonnet term and a negative cosmological constant. The event horizon of these topological black holes can be a hypersurface with positive, zero or negative constant curvature. When the horizon is a zero curvature hypersurface, the thermodynamic properties of black holes are completely the same as those of black holes without the Gauss-Bonnet term, although the two black hole solutions are quite different. When the horizon is a negative constant curvature hypersurface, the thermodynamic properties of the Gauss-Bonnet black holes are qualitatively similar to those of black holes without the Gauss-Bonnet term. When the event horizon is a hypersurface with positive constant curvature, we find that the thermodynamic properties and phase structures of black holes drastically depend on the spacetime dimension \(d\) and the coefficient of the Gauss-Bonnet term: when \(d\ge 6\), the properties of black hole are also qualitatively similar to the case without the Gauss-Bonnet term, but when \(d=5\), a new phase of locally stable small black hole occurs under a critical value of the Gauss-Bonnet coefficient, and beyond the critical value, the black holes are always thermodynamically stable. However, the locally stable small black hole is not globally preferred, instead a thermal anti-de Sitter space is globally preferred. We find that there is a minimal horizon radius, below which the Hawking-Page phase transition will not occur since for these black holes the thermal anti de Sitter space is always globally preferred.