We derive a simple no-go theorem relating to self-tuning solutions to the cosmological constant for observers on a brane, which rely on a singularity in an extra dimension. The theorem shows that it is impossible to shield the singularity from the brane by a horizon, unless the positive energy condition (p + p greater than or equal to 0) is violated in the bulk or on the brane. The result holds regardless of the kinds of fields which are introduced in the bulk or on the brane, whether Z(2) symmetry is imposed at the brane, or whether higher derivative terms of the Gauss-Bonnet form are added to the gravitational part of the action. However, the no-go theorem can be evaded if the three-brane has spatial curvature. We discuss explicit realizations of such solutions which have both self-tuning and a horizon shielding the singularity.