Randolph Carter dreams three times of a majestic sunset city, but each time he is abruptly snatched away before he can see it up close. When he prays to the gods of dream to reveal the whereabouts of the phantasmal city, they do not answer, and his dreams of the city stop altogether. Undaunted, Carter resolves to go to Kadath, where the gods live, to beseech them in person. However, no one has ever been to Kadath and no one even knows how to get there. In dream, Randolph Carter descends "seventy steps" and speaks of his plan to the priests Nasht and Kaman-Thah, whose temple - the Cavern of Flame - borders the Dreamlands. The priests warn Carter of the great danger of his quest and suggest that the gods withdrew his vision of the city on purpose.
The quest begins
Carter enters the Enchanted Wood and meets the zoogs, a race of predatory and sentient rodents. For a novice, such an encounter could prove calamitous, but Carter is an experienced dreamer and so is knowledgeable of their language and customs. When Carter asks the zoogs about Kadath, they don't know where it is; instead, they suggest that Carter go to the town of Ulthar to find a wizened priest named Atal who is learned in the ways of the gods.
In the cat-laden city of Ulthar, Carter visits Atal, who mentions a huge carving wrought on Ngranek's hidden side that shows the features of the gods. Carter realizes that if he can go to Ngranek, examine the carving, and then find a place where mortals share those features and are thus related to the gods, he must be near Kadath.
Voyage to Oriab Isle
Carter goes to Dylath-Leen to secure passage to Oriab. Dylath-Leen is infamous for the black galleys that frequent its harbors. These galleys are steered by oarsmen who are never seen and crewed by turbaned men that trade curious-looking rubies for slaves and gold.
Randolph Carter's quest is interrupted when he is captured by the turbaned men and flown to the moon on one of their notorious black galleys. Once there, he learns that the turbaned men are slaves to the terrifying moon-beasts. A procession of moon-beasts and their slaves escort Carter across the moon to deliver him to the Crawling Chaos Nyarlathotep (one of the Outer Gods who rule space, in contrast to the Great Ones, the gods of earth). He is saved by the cats of Ulthar, who slay his captors and return Carter to earth's Dreamlands in the port of Dylath-Leen.
Carter boards a ship sailing to Baharna, a great seaport on the isle of Oriab. On the way to Oriab and while he travels across the island riding a zebra, Carter hears dark whispers about the night-gaunts, though they are never properly described. Carter makes a treacherous climb across Ngranek and discovers the gigantic carving of the gods on its far side. He is surprised to see that the features match those of sailors who trade at the port of Celephaïs, but before he can act on this knowledge, he is snatched away by the night-gaunts and left to die in the Vale of Pnath in the underworld.
Carter is rescued by friendly ghouls, amongst them Richard Pickman, a friend of Carter's, the protagonist of another of Lovecraft's stories, Pickman's Model, and who is now also a ghoul, who agree to return him to the upper Dreamlands. They make their way to the terrible city of the gugs to reach the Tower of Koth, wherein a winding stairway leads to the surface. Finding the city asleep, Carter and the ghouls attempt to sneak past the snoring gugs. The ghasts, the gugs' traditional enemies, begin an attack, but the group manages to ascend the stairway and open the great trapdoor to the Enchanted Wood.
Journey to Celephaïs
Here Carter comes upon a gathering of zoogs and finds that they plan to make war on the cats of Ulthar. Not wanting to see his friends harmed, Carter warns the cats, enabling them to launch a surprise attack on the zoogs. After a brief skirmish, the zoogs are defeated. To abate further hostilities, the zoogs agree to a new treaty with the cats of Ulthar.
Carter reaches the city of Thran and buys passage on a galleon to Celephaïs. While en route, Carter asks the sailors about the men who trade in Celephaïs—the ones he believes to be kin to the gods. He learns that they are from the cold, dark land of Inquanok or Inganok and that few people dare to travel there. Even more ominous, there are no cats there. The plateau of Leng with its inhuman treacheries is too near.
In Celephaïs, Carter meets his old friend Kuranes, the king of the city. Kuranes is an old dreamer whom Carter knew in the waking world, but when he died, he became a permanent resident of the Dreamlands. Longing for home, he has dreamed parts of his kingdom to resemble his native Cornwall. Kuranes knows the pitfalls of the Dreamlands all too well and tries to dissuade Carter from his dangerous quest. Carter, however, will not be deterred.
Trek into the Cold Waste
Under the pretense of wishing to work in its quarries, Carter boards a ship bound for Inganok, a nation built of onyx. The trip to Inganok takes three weeks, but as they draw near, Carter spots a strange granite island. When he inquires about the mysterious isle, the captain explains that it is the nameless rock, and it is best to not speak of it. That night, Carter hears strange howls from the nameless island.
When Carter arrives at Inganok, he purchases a yak and heads northward, in the hope that past the onyx quarries he will find Kadath. Carter ascends a steep ridge beyond which nothing is visible but sky. At the summit, he looks out and gets a breathtaking view of a gargantuan quarry. Carter sets off toward this quarry, but his yak, spooked, abandons him.
Carter is captured by a slant-eyed man, whom he has met before among the merchants of Dylath-Leen. The slant-eyed man summons a shantak-bird, which both ride over the Plateau of Leng, a vast tableland populated by Pan-like beings. Arriving at a monastery wherein dwells the dreaded High Priest Not to Be Described, Carter now suspects that the slant-eyed man is yet another conspirator of the forces that seek to thwart his quest.
The slant-eyed man leads Carter through the monastery to a domed room with a circular well, which Carter speculates leads to the Vaults of Zin in the underworld. Herein, the high-priest, wearing a silken robe and a mask, is waiting. Carter learns that the Men of Leng are the same beings that conceal their horns under turbans and trade in Dylath-Leen. He also learns that the night-gaunts do not serve Nyarlathotep as is commonly supposed, but Nodens, and that even Earth's Gods are afraid of them. It is never revealed to the reader who the high-priest in the silken mask is, but Carter recoils from it in horror.
When the slant-eyed man is momentarily distracted, Carter pushes him into the well and escapes through the maze-like corridors. In pitch-black darkness, Carter wanders through the monastery, fearing he is being pursued by the High Priest Not to Be Described. At last reaching the outside, Carter realizes that he is in the ruins of ancient Sarkomand, which lies near the coast.
Soon he encounters the ghouls that helped him earlier once more. The Men of Leng have taken them hostage on their ship, and they are to be taken to the nameless rock, revealed to be a moon-beast outpost. Carter summons the rest of the ghouls from the underworld and they take control of the galley. After releasing their kin, they sail on to the nameless rock and fight a pitched battle against the moon-beasts. Emerging victorious, and fearing the arrival of reinforcements, Carter and the ghouls return to Sarkomand. Once there, Carter obtains the services of a flock of night-gaunts to transport himself and the ghouls to the gods' castle on Kadath.
After an exhilarating flight, Carter arrives at last at the abode of the gods, but finds it empty. Finally a great procession arrives with much fanfare, led by a pharaoh-like man who explains to Carter that the gods of earth have seen the city of Carter's dreams and decided to make it their home, and have thus abandoned Kadath. The gods walk no more in the ways of gods, and have become instead mere denizens of the jewelled city Carter had glimpsed in his dreams, which is nothing but childhood memories of his home city of Boston. "It is not over unknown seas," he says, "but back over well-known years that your quest must go; back to the bright strange things of infancy and the quick sun-drenched glimpses of magic that old scenes brought to wide young eyes. For know you, that your gold and marble city of wonder is only the sum of what you have seen and loved in youth... These things you saw, Randolph Carter, when your nurse first wheeled you out in the springtime, and they will be the last things you will ever see with eyes of memory and of love." This mysterious man then reveals his identity—he is Nyarlathotep, the Crawling Chaos, the emissary of the Other Gods who dwell in the blackness of space.
Nyarlathotep sends Carter on a great Inganok shantak-bird through space to the sunset city. Unfortunately, Carter realizes too late that the mocking Nyarlathotep has tricked him, and that instead he is being taken to the court of Azathoth at the center of the universe. At first believing he is doomed, Carter suddenly remembers that he is in a dream and saves himself by leaping from the great bird. As he falls, his thoughts turn toward New England, and he wakes to find that he is no longer in the Dreamlands but in his own room in the waking world of Boston, looking out upon its architectural graces, suffused in a splendid sunrise.
The final lines of the story find Nyarlathotep brooding over his defeat within the halls of Kadath, mocking in anger the "mild gods of earth" whom he has snatched back from the sunset city.