"Down in the Bottomlands" is a novella written by Harry Turtledove.
It won the Hugo Award for Best Novella in 1994. The story takes place in an alternative history in which the point of divergence occurs 5.5 million years ago during the Miocene Epoch when the Atlantic Ocean did not reflood the Mediterranean Sea, as it did in our history. The Mediterranean Basin thus remains dry to the present day in this time line, as a vast sunken desert called the Bottomlands, averaging nearly two kilometers below mean sea level, with summer temperatures reaching well above 40 °C (104 °F) and with little to no rainfall, and brine lakes.
Plot.
The story concerns a field biologist working at "Trench Park" named Radnal vez Krobir. He is a citizen of Tartesh, a "Homo neanderthalensis" nation which seems to take in much of the west part of the Bottomlands and what in the real world is France and Spain. He is doing a two-year stint as a field guide to tourists from his and other nations who are visiting the Park to see the plants and animals there. During one of those tours, a military officer of the "Kingdom of Morgaf" (real-world British Isles) is killed by one of the other tourists in his party. 
Radnal must call higher authorities to investigate the matter, and in the course of their investigation, they determine that the deceased man had a microprint in his effects outlining a plot by another nation to set off a "starbomb" (a nuclear weapon) near the "Barrier Mountains" (a range of mountains joining the Sierra Nevada and the Rif across where the real-world Strait of Gibraltar is located). This would have affected one of the many geologic faults in the area, knocking a gap in the mountains and flooding the Bottomlands to form a new central sea. This had been apparently instigated by the Krepalga (a "Homo sapiens" nation occupying all or part of the Middle East, which would have benefited by having a real-world-type Mediterranean Sea at to its west border).
Radnal and other characters eventually find who killed the Morgaffo officer, and with the unwitting help of a koprit bird (similar to a shrike) native to the Park, track down the location of the bomb, where it is defused. Koprit birds apparently have a habit of stealing bright shiny things; it stole the detonator wire from the bomb and used it to decorate its food-hoard bush to attract a mate, as the wire had been disguised as jewelry to smuggle it in past security.
The conspirators had sabotaged all the tour party's transport, leaving them stranded far below sea level on the hot dry abyssal plain. This leaves a task force of Tarteshan secret police, the regular police, and the army with the job of evacuating the tour party, by giving each member a big backpack tank of drinking water and marching them out. Partway up to sea level a helicopter finds them and flies the party the rest of the way.
The story ends with Radnal being honored by the "Hereditary Tyrant" (i.e., King) of Tartesh at a great festival in Tartesh's capital Tarteshem, for saving the Bottomlands from certain destruction. There he meets again a woman named Toglo zev Pamdal, who was in his tour party. She had told him she was a "distant collateral relative" of the Hereditary Tyrant but it turns out is actually his niece. They shake hands at the story's conclusion and presumably begin a romantic relationship.
The story is told from Radnal's point of view, to include descriptions of Trench Park and its animals and plants to the tourists. Through these descriptions, the reader comes to understand the unique geography and ecosystem contained within the Bottomlands and its Trench, and how animals and plants would have adapted to a desert environment two kilometers below average sea level. The reader can also see how the geography of the area would have been different from our timeline, including things like deep river canyons as the rivers around the Mediterranean would have incised such canyons in their descent down the old continental shelf; hydroelectric dams on such rivers generated 80% of Tartesh's electricity.
Publication history.
The novella was first printed in January 1993 in the magazine "Analog" and has been reprinted thrice since then: the first time in 1997 in "The New Hugo Award Winners, Volume IV"; the second time in 1999 with two other novellas in a book called "Down in the Bottomlands and Other Places"; and the third time in 2015 in a collection of Turtledove's short fiction and essays entitled "We Install and Other Stories".
References.
 ;templatestyles src="Reflist/styles.css" / ;