We investigate the thermodynamics of static black objects such as black holes, black strings and their generalizations to D dimensions (`black branes') in a gravitational theory containing the four dimensional Gauss-Bonnet term in the action, when D-4 of the dimensions are compactified on a torus. The entropies of black holes and black branes are compared to obtain information on the stability of these objects and to find their phase diagrams. We demonstrate the existence of a critical mass, which depends on the scale of the compactified dimensions, below which the black hole entropy dominates over the entropy of the black membrane.