In this letter, an enhanced version of Address Resolution Protocol (ARP) is proposed to prevent ARP poisoning-based Man-in-the-Middle (MITM) attacks. The proposed mechanism is based on the following concept. When a node knows the correct Media Access Control (MAC) address for a given IP address, if it retains the IP/MAC address mapping while that machine is alive, then MITM attack is impossible for that IP address. In order to prevent MITM attacks even for a new IP address, a voting-based resolution mechanism is proposed. The proposed scheme is backward compatible with existing ARP and incrementally deployable.