 Another story relates how Dunstan nailed a horseshoe to the Devil 's hoof when he was asked to re @-@ shoe the Devil 's horse . This caused the Devil great pain , and Dunstan only agreed to remove the shoe and release the Devil after he promised never to enter a place where a horseshoe is over the door . This is claimed as the origin of the lucky horseshoe . 
