By a simple modification of Hawking's well-known topology theorems for black hole horizons, we find lower bounds for the areas of smooth apparent horizons and smooth cross-sections of stationary black hole event horizons of genus $g>1$ in four dimensions. For a negatively curved Einstein space, the bound is ${{4\pi (g-1)}\over {-\ell}}$ where $\ell$ is the cosmological constant of the spacetime. This is complementary to the known upper bound on the area of $g=0$ black holes in de Sitter spacetime. It also emerges that $g>1$ quite generally requires a mean negative energy density on the horizon. The bound is sharp; we show that it is saturated by certain extreme, asymptotically locally anti-de Sitter spacetimes. Our results generalize a recent result of Gibbons.