Peer-to-Peer (P2P) protocols usage is proliferating for a variety of applications including time-and safety-critical ones. While the distributed design of P2P provides inherent fault tolerance to certain failures, the large-scale decentralized coordination exhibits various exploitable security threats. One of these key threats are Eclipse attacks, where a large fraction of malicious peers can surround, i.e., eclipse benign peers. Topology-aware localized Eclipse attacks (taLEAs) are a new class of such attacks that allows for highly efficient denial of service attacks with a small amount of malicious resources. Our contribution is twofold: First, we show the generic susceptibility of structured P2P protocols to taLEAs. Second, we propose a new lookup mechanism for the proactive and reactive detection and mitigation of such attacks. Our novel lookup mechanism complements the common deterministic lookup with randomized decisions in order to reduce the predictability of the lookup. We validate our proposed technique via extensive simulations, increasing the lookup success to 100% in many scenarios. © 2014 IEEE.