The lost City of Atlantis, written about by Plato 2600 years ago, did say that the Island was situated near "The Pillars of Hercules"
Which is believed to describe the Mediteranean "Straits of Gibralter"...today.

Now, a U.S.-led research team may have finally located the lost city of Atlantis, the legendary metropolis believed swamped by a Tsunami thousands of years ago in mud flats in southern Spain.
"It is just so hard to understand how the power of a Tsunami can wipe out a city 60 miles inland, but that's pretty much what we're talking about," said Freund, a University of Hartford, Connecticut, professor who lead an international team searching for the true site of Atlantis.

To solve the age-old mystery, the team used a satellite photo of a suspected submerged city to find the site just north of Cadiz, Spain. There, buried in the vast marshlands of the Dona Ana Park, they believe that they pinpointed the ancient, multi-ringed dominion known as Atlantis.
The team of archeologists and geologists in 2009 and 2010 used a combination of deep-ground radar, digital mapping, and underwater technology to survey the site.
Tsunamis in the region have been documented for centuries, Freund says. One of the largest was a reported 10-story tidal wave that slammed Lisbon in November, 1755.

Debate about whether Atlantis truly existed has lasted for thousands of years. Plato's "dialogues" from around 360 B.C. are the only known historical sources of information about the iconic city. Plato said the island he called Atlantis "in a single day and night... disappeared into the depths of the sea."

http://www.reuters.com/article/2011/03/12/us-tsunami-atlantis-idUSTRE72B2JR20110312

We have all seen over the past few days how destructive a tsunami can be, but I suspect that a bit of tectonic subsidence might have been needed as well.