Well, the story can't be literally true. A continent the size of Australia will not fit "within the straits of Gibraltar", because its area, of almost three million square miles, is several times larger than the entire Mediterranean Sea, which is just under a million square miles.
However, there is an event in the ancient past that could explain all of this. Geology shows that the Straits of Gibraltar have opened and closed several times in the last few million years, and when they are closed, the Mediterranean will mostly evaporate within a thousand years. The last time they opened, the Zanclean flood refilled the Mediterranean in about a year.
The dry bed of the Mediterranean would have been a strange environment, with vast deposits of salt and lakes of brine, unsuitable for modern-day animals and plants. However, it would have been very suitable for the creatures that worshipped the Crawling Chaos, who have survived in artificial habitats beneath the bottom of the sea, waiting for the stars to be right and make their ritual possible.
When that time finally came, the effects were drastic.
The closure of Gibraltar happened via massive earthquakes in Spain, Portugal, Algeria and Morocco. The British territory of Gibraltar was entirely destroyed. The tsunami in the Mediterranean stripped the Balearic Islands back to bedrock and did vast damage on the western coasts of Corsica, Sardinia and Sicily. Flooding occurred throughout the Mediterranean coastline, which was unprepared because of the absence of significant tides within the inland sea. In the North Atlantic, the Azores and Canary Islands survived rather better and the tsunami was weak by the time it reached North America.
The Turkish Straits and Suez Canal became rapids within a few weeks as evaporation began to lower the sea level of the Mediterranean. This disrupted commerce within Turkey and the Black Sea region, and between the Mediterranean region and Africa, India, China and Japan, and the closure of Gibraltar became a world-wide crisis. The idea of re-opening the strait before evaporation lowered the sea very far united all of Europe and Russia, plus Egypt and Israel, for a wide variety of reasons. Other countries came around to the idea as the effects on trade became clear.
Spain and Morocco made it clear that after the devastation they had suffered, using nuclear weapons to re-open the straits was not going to be welcome, not even a little, and one of history's largest excavation projects was started.
Humanity is unaware of why or how Gibraltar was deliberately closed, but it seems likely that a war will break out between them and the followers of the Creeping Chaos, once the ancient horrors notice that excavation is underway.