In contrast to asymptotically flat black hole solutions for which all horizons settle down rapidly to have the topology of a sphere, certain asymptotically anti-de Sitter black hole solutions have horizons with the topology of a higher genus surface. The fact that the nontrivial topology of these horizons is not hidden might appear to indicate that generalizations of topological censorship do not hold for such spacetimes. However, this is not the case: topological censorship holds in anti-de Sitter spacetimes. Specifically, we prove every causal curve with endpoints on scri can be deformed to a curve at scri. From this it follows that the genus of the black hole horizon is set by the large scale topology of the spacetime. Our results clarify the connection between topological censorship and the non-spherical horizon topologies of locally anti-de Sitter black holes. Furthermore, the proof making this connection is valid for any spacetime that satisfies the principle of topological censorship. ©1999 American Institute of Physics.