The book is divided into three parts.

Sailing to the Future edit

The story begins with Elric lost somewhere in the Young Kingdoms and near the sea. A mysterious ship appears and he is welcomed aboard by its captain and introduced to three other powerful warriors. The captain informs the adventurers that they are traveling across time and between realities. They have been found because they alone have the power to stop alien sorcerers from destroying their worlds. They come to understand that they (Elric, Erekosë, Dorian Hawkmoon, and Corum Jhaelen Irsei) are Eternal Champions and are actually four different iterations of the same being. The Champions are instructed that they must slay the evil beings and destroy their building by fire. Upon finding the dwelling place of the creatures, they face many dangers within. The Champion finds a sentient pool in a well that seems to be trying to communicate to its partner. The four Champions assimilate into one eight-armed being, and destroy the creature in the pool, only to discover that the 'building' they have invaded is the body of the other creature. They destroy it and go their separate ways, with the memory of what happened fading like a dream.

Sailing to the Present edit

Elric finds himself on another shore without the memory of his last adventure. He meets a sailor called Count Smiorgan Baldhead who accompanies Elric as they are followed by a mysterious, riderless horse. Elric and Smiorgan find that they are in another world, one inhabited by a Melnibonéan nobleman named Saxif D’an. Saxif recognizes Elric but does not honor his sovereignty in this realm. Saxif is the subject of an old Melnibonean tale. In the legend, Saxif loved a half-human woman but she loved another; Prince Carolak. In the legend, Saxif kills the woman rather than see her with another, only to learn with her dying breath that she still loved him. Saxif is now obsessed with a woman, Vassliss, who resembles his dead love and Prince Carolak reveals himself on a horse and defeats Saxif.

Sailing to the Past edit

Elric and Smiorgan, after passing through the Crimson Gate, are saved from drowning by Duke Avan and his men. Duke Avan is travelling to find R’lin K’Ren A’a, the ancestral city of the Melnibonéans, where he seeks two rare gems purported to be the eyes of a large jade statue of Arioch. Elric and Smiorgan decide to join him on the voyage.

Using a map that Duke Avan has procured, the group crosses the boiling sea and finds the island marked on the map where R’lin K’Ren A’a is located. They enter the mouth of a river to head inland on the island. Along the river they are attacked by reptilian savages with human features and stork-like legs who hurl sharp crystalline disks from clubs. Losing the battle and with defeat imminent, Elric summons aid from King Nnuuurrrr’c’c of the Insects. Nnuuurrrr’c’c hears his summons and sends a swarm of giant dragonflies who annihilate the reptilian savages.

Elric, Smiorgan, Duke Avan, and the surviving crewman eventually find the island within the island where R’lin K’Ren A’a lies according to the map. They disembark from the ship into the jungle and eventually find the city. At the city they also find the great jade statue of Arioch, but the eyes are missing. The group is suddenly attacked by the reptilian savages again and Elric summons aid from Arioch who refuses to help.

The group flees into an intact building in the ruins to escape their attackers. In the building they find a message that appears to have been recently scribed. They emerge from the other side of the building into the central square of the city where they see two glass dome structures. Then they run into the nearest structure to again escape the pursuing savages where the group then becomes separated from each other.

Lost in the maze of the crystal structure, Elric and the others are saved by a naked man named J’osui C’reln Reyr who is revealed to be a 10,000-year-old man known from legend as the Creature Doomed to Live. J’osui hides them from the savage reptiles, whom he calls the Olab, and reveals that the crystal structure they were in is one of the eyes of the jade statue of Arioch. Elric learns from J’osui why he is cursed to live and why Elric’s ancestors were forced to leave R’lin K’Ren A’a for Melniboné. He also learns how he can end the curse by summoning Arioch to possess the jade statue and cause it to leave the city.

They return to the jade statue and Elric begins the ritual to summon Arioch. During the ritual, Stormbringer compels Elric to slay Duke Avan and a remaining crewman so that Arioch will heed the summons. Arioch comes, possess the statue, and it leaves the city with its eyes intact. Stormbringer then leaps from Elric’s hand and slays J’osui C’reln Reyr. Elric and Smiorgan depart the city and find another ship laden with treasure that J’osui had informed them of, then sail away from the island.