Geesh I seem to talk about Game of Thrones a lot. This is one of the coolest theories I have unearthed whilst unemployed. It doesn't really have any plot spoilers, it's all just conjecture about the history of the world asoiaf takes place in.
Before the Targaryeans, before the Andals, and the First Men, before the giants and the children of the forest, Westeros was inhabited by the Deep Ones.
In Oldtown, there sits a tower called Hightower. The base of the tower differs from the upper levels, and predates them by "thousands of years."
...its massive walls and labyrinthine interiors are all of solid rock, with no hint of joins or mortar, no chisel marks of any kind. [...]The fused black stone of which it is made suggests Valyria but the plain, unadorned style of architecture does not...the narrow, twisting, windowless passages strike many as being tunnels rather than halls; it is very easy to get lost amongst their turnings.
Many maesters believe the fortress to be Valyrian but if this is true then the dragonlords came to Westeros thousands of years before they ever had an outpost on Dragonstone. And as just noted in the passage above, the architecture is not very Valyrian.
A one Maester Theron (who seems half-deranged from the way his work Strange Stone is described) claims the structure is built by the Deep Ones: "a queer, misshapen race of half men sired by creatures of the salt seas upon human women." He notes the similarity, both in construction and origin, between this fortress in Oldtown and the Seastone Chair on the Iron Islands.
The Seastone Chair is described as being "carved into the shape of a kraken from an oily black stone" AND "was said to have been found by the First Men when they first came to Old Wyk." So now we have two pieces of construction that look similar, no one knows where they came from or how old they are, and, for what it's worth, are both directly on the ocean and on the Western side of Westeros.
Archmaester Haereg once advanced the interesting notion that the iron born came from some unknown land west of the Sunset Sea, citing the legend of the Seastone Chair.
That would make sense if some Iron Born predecessor came from the west and built their first settlements along the western side of Westeros. But what is west of Westeros? No one knows.
What we do know is this:
I am going to assume that the world asoiaf takes place in is round. So that if you kept heading east on that map you'd pop back around by Westeros eventually (we all know how maps work). The city on the south east corner I have circled is Asshai, a dark, creepy city full of magic and death.
Even the Asshai'i do not claim to know who built their city; they will say only that a city has stood here since the world began and will stand here until it ends. Travelers tell us that the city is built entirely of black stone…Some say that the stone of Asshai has a greasy, unpleasant feel to it, that it seems to drink the light…
Greasy black stone of mysterious origin sure sounds like our oily black stone of mysterious origin. Could it be these prehistoric fish men came from Asshai to Westeros? Or is Maester Theron just crazy and did some other ancient civilization come out of Asshai and build on Westeros thousands of years before the First Men?
There's actually more evidence it was the fish men. There are slimy black stones on Yeen and and the Isle of Toads.
Maesters and other scholars alike have puzzled over the greatest of the enigmas of Sothoryos, the ancient city of Yeen. A ruin older than time, built of oily black stone, in massive blocks so heavy that it would require a dozen elephants to move them, Yeen has remained a desolation for many thousands of years, yet the jungle that surrounds it on every side has scarce touched it. ("A city so evil that even the jungle will not enter," Nymeria is supposed to have said when she laid eyes on it, if the tales are true). Every attempt to rebuild or resettle Yeen has ended in horror.
On the Isle of Toads can be found an ancient idol, a greasy black stone crudely carved into the semblance of a gigantic toad of malignant aspect, some forty feet high. The people of this isle are believed by some to be descended from those who carved the Toad Stone, for there is an unpleasant fishlike aspect to their faces, and many have webbed hands and feet. If so, they are the sole surviving remnant of this forgotten race.
And legends of creatures emerging from the sea pop up in a couple other intriguing places. Like in Lorath:
Some have suggested that mayhaps the mazemakers were born of interbreeding between human men and giant women. We do not know why they disappeared, though Lorathi legend suggests they were destroyed by an enemy from the sea: merlings in some versions of the tale, selkies and walrus-men in others.
This passage connects the "enemy from the sea" to two of the other greasy black stone ruins. If the Mazemakers were as large as the legends say it would explain the giant stones in Yeen that need "a dozen elephants" to move them and the maze-like passages at the base of Hightower in Oldtown; perhaps the Deep Ones stole some of the maze-building secrets from their conquered peoples and used slave labor to build their giant structures.
Finally there is a more mysterious ancient presence of the Deep Ones on the Thousand Islands east of Ib.
a sea-grit scatter of bleak windswept rocks believed by some to be the last remnants of a drowned kingdom whose towns and towers were submerged beneath the rising seas many thousands of years ago[...]The people of these islands...are said to sacrifice sailors to their squamous, fish-headed gods[...]Though surrounded by water on all sides, these islanders fear the sea so much that they will not set foot in the water even under threat of death.
Our pre-human fish seem to have been nothing short of a global empire. Apparently even taking on a god-like status in the Thousand Islands.
Who were these guys?? Besides these crazy ruins mentioned in A World of Ice and Fire, do they have anything to do with "modern day" Westeros? To that I say, let us look at the religion of the Iron Islands.
“We did not come to these holy lands from godless lands across the seas," the priest Sauron Salt-Tongue once said. "We came from beneath those seas, from the watery halls of the Drowned God who made us in his likeness and gave to us dominion over all the waters of the earth.”
The religion of the Drowned God says that the Ironborn came from the sea, which makes them fish-men after a fashion. Most telling of all are the words of House Greyjoy: We Do Not Sow. We do not grow things. Where else do things not grow? Not in Asshai where "little grows", or the ancient ruins of Yeen which the jungle around it has not touched though it's been sitting there for thousands of years.
In fact, in A Feast for Crows, Nimble Dick of Cracklaw Point claims the Deep Ones (though he calls them Squishers) are still around. Today. In Westeros.
They look like men till you get close, but their heads is too big, and they got scales where a proper man's got hair. Fish-belly white they are, with webs between their fingers. They're always damp and fishy-smelling, but behind those blubbery lips they got rows of green teeth sharp as needles. Some say the First Men killed them all, but don't you believe it. They come by night and steal bad little children, padding along on them webbed feet with a little squish-squish sound. The girls they keep to breed with, but the boys they eat, tearing at them with those sharp green teeth.
And finally, might not these strange fish-men be the reason for Patchface's unexplained survival for two days at sea after a shipwreck? And as to why he now talks about "under the sea" a whole lot, and makes cryptic, but accurate prophecies?
I like this theory in particular because the hints are rare and somewhat subtle and I am doubtful they will have any lasting impact on the plot of the series. They're simply there to add richness if you're someone who is unemployed re-reading the series looking for exactly these sorts of easter eggs. Time and again, George R. R. Martin shows his mastery of providing depth and mystery to the magical universe of Westeros.
I'm sure I haven't uncovered all these fishy clues. I connected a lot of these dots myself but I would be remiss if I didn't give credit to this reddit thread and this a Wiki of Ice and Fire page for sending me off deeper into the abyss of this mystery.
Finally, I know the Deep Ones is a nod from GRRM to H.P.Lovecraft, but alas, I am not familiar with his works. All I know is he has something to do with Cthulhu.
Edit: I posted this on Reddit and it sparked some good discussion!