In the Odyssey of Homer , legend says that , after the Trojan War , a Greek official named Menestheus escaped with his troops through the Straits of Gibraltar . They got to the Guadalete River and created a port . According to the legend told in the Odyssey of Homer , after the Trojan War a Greek official named Menestheus escaped with his troops through the Straits of Gibraltar and reached the Guadalete River .