Neutrino telescopes of kilometer size are currently being planned. They will be two or three orders of magnitude bigger than presently operating detectors, but they will have a much higher muon energy threshold. We discuss the trade-off between area and energy threshold for indirect detection of neutralino dark matter captured in the Sun and in the Earth and annihilating into high energy neutrinos. We also study the effect of a higher threshold on the complementarity of different searches for supersymmetric dark matter.