According to legend, before ONDUN (the creator of all things) departed from the world, He sent out His sons AIDEN and UREC each in a separate great arkship to explore His entire creation, while His third son, JORON, remained behind in the Eden-like land of Terravitae.
Today, the known world has two continents, Tierra and Uraba, connected by a thin isthmus of land, on which the sacred city of Ishalem was built. The people of Tierra believe themselves to be the descendants of Aiden's crew, while Urabans are convinced that their ancestors originally sailed on Urec's ship. The wreck of an ancient vessel sits on a high hill in Ishalem, and each people insists it belongs to them.
After generations of strife, KING KORASTINE of Tierra and SOLDAN-SHAH IMIR of Uraba agree to sign an Edict that divides the world in half, above and below Ishalem. This will remove all need for conflict, and both leaders look forward to peace at last. Korastine sails from Calay, the capital of Tierra, with his young daughter PRINCESS ANJINE and her childhood friend, MATEO. Soldan-Shah Imir sails from Olabar, Uraba's capital, for the formal signing ceremony.
King Korastine and Soldan-Shah Imir meet at the wreck of the Arkship on the hill above Ishalem, accompanied by PRESTER-MARSHALL BAINE (representing the Aidenist church) and UR-SIKARA LUKAI (representing the Urecari church). The Edict is signed, peace is declared between the two continents, and the celebrations begin.
Back at the Olabar palace, Imir has left his son and heir, OMRA, in charge. Omra's beloved wife ISTAR is pregnant and will soon bear their first child. The sikaras—priestesses of the church of Urec—bless the unborn baby, and Omra is very happy. His cousin BURILO comes from the distant soldanate of Missinia to deliver the head of a slain bandit leader from the Great Desert; the bandits have been plaguing the soldanate for years, but though their leader is dead, Omra knows the problem isn't solved. Before Soldan-Shah Imir can return from signing the Edict in Ishalem, tragedy strikes: Istar collapses and dies from a difficult miscarriage. Omra is devastated.
In Ishalem, we meet PRESTER HANNES, a fanatical follower of the Aidenist church, who has spent years in disguise among the Urecari. He was given this spying mission by Prester-Marshall Baine to gather information about the rival religion. Hannes hates the followers of Urec with a passion. During the celebrations after the signing ceremony, an accidental fire starts and quickly spreads across the city. Both Tierrans and the Urabans assign blame for the disaster and spend more time fighting each other than trying to extinguish the fire. As flames rage through the main Urecari church, Prester Hannes breaks in to steal a religious relic. In the process, he is caught in the inferno, terribly burned, and barely manages to stagger away, delirious.
Korastine flees the city with Anjine and Mateo, while Soldan-Shah Imir calls for an evacuation of his people. On her way to the harbor to escape the fire, ASHA (one of Imir's wives) finds the injured Prester Hannes; believing him to be a devout follower of Urec because of his tattered clothes and the Urecari relic he took from the burning church, she decides to bring him along and nurse him back to health. As Korastine and Imir sail away in opposite directions, the holy city of Ishalem burns behind them, and both leaders know the war is just beginning….
The young Tierran sailor CRISTON VORA and his new wife ADREA sail his cargo boat from the coastal fishing village of Windcatch to Calay. Criston dreams of sailing the seas and visiting new lands and, though he hates to leave lovely Adrea behind, joins the crew of the new exploration ship, the Luminara; CAPTAIN ANDON SHAY plans to sail to the edge of the world and find the lost land of Terravitae and Holy Joron. Criston sells his boat so Adrea will have money to support herself while he's away; she gives him a lock of her hair, and he promises to write her letters, which he'll throw overboard in bottles. The sympathetic magic binding the hair to Adrea should bring the bottles to her. She says farewell, and the Luminara sails off. Only after she goes back to Windcatch to live with her younger brother CIARLO (who has a lame leg) and Criston's old mother does Adrea discover that she's pregnant….
Another group of people, followers of neither Aiden nor Urec, are the Saedrans—scientists, craftsmen, philosophers. They believe their ancestors left Terravitae voluntarily, long after the two brothers sailed, and settled on another continent, from which they established a maritime civilization. But the Saedran continent sank beneath the waves, and the only survivors are the descendants of traders who were away from home at the time of the catastrophe. Saedrans have settled in both Uraba and Tierra but don't espouse either religion.
One young Saedran in Calay, ALDO NA-CURIC, is being trained by the old scholar SEN LEO NA-HADRA to become a chartsman (a navigator much in demand by ship captains). Aldo passes his test, having memorized all of the generations of navigational data as well as volumes of the Tales of the Traveler—journals written by a mysterious wandering stranger, said to be either Aiden or Urec himself. Excited to become a chartsman, Aldo goes to the Calay docks, where he meets the con man YAL DOLICAR, who sells him a fake map of unexplored lands. When Aldo eagerly shows Sen Leo his discovery, the scholar denounces Dolicar's map as a forgery, and then proves it by taking Aldo to a secret chamber beneath the Saedran temple. There, covering the walls and ceiling, is an intricate map of everything the Saedrans have compiled about the world: the Mappa Mundi, or the Map of All Things.
In Olabar, Asha nurses the burned Prester Hannes back to health, praying over him, giving him Urecari sacraments. When he recovers his strength and learns that she has fouled him with the hated rival religion, Hannes becomes enraged, kills her, and escapes into the night. Grief-stricken to learn that his young wife was murdered by the mysterious man she tried to help, Soldan-Shah Imir calls out his guards… but Hannes is gone.
Omra is despondent over having lost his own young wife Istar, but his father arranges another wife for him, CLIAPARIA, the daughter of the Yuarej soldan. Though she is beautiful and ambitious, he cannot bring himself to love her. Instead, Omra fixes his anger on the Tierrans for burning Ishalem. Many in Uraba feel the same rage and call out for war. Soldan-Shah Imir increases production of metals at the Gremurr mines, a secret facility on a rugged coast that should technically belong to Tierra, but is inaccessible to them due to a mountain range. Because Uraba is poor in metals, the people are forced to mine the ores in enemy territory.
Hoping to rebuild Ishalem, Prester-Marshall Baine and a group of volunteers from Tierra set up camp in the burned ruins and set to work clearing away the rubble. They are beset by an angry Uraban soldan, who feels the Tierrans are further desecrating the holy city. Baine and his followers are murdered horribly, and only one man, an Iborian shipbuilder named KJELNAR, escapes to tell the tale. When King Korastine learns what has happened to the well-meaning Aidenists, he has no choice but to prepare for all-out war. Though his ward Mateo is still young, he sends the young man off to be trained in the Tierran military, while his daughter Anjine will have to study to be a leader, the next queen.
Learning of the ill-advised massacre at Ishalem, Soldan-Shah Imir dispatches a diplomat with an apology and a proposed peace treaty to Korastine, but the diplomat is intercepted by TAVISHEL, destrar of Soeland Reach, who brashly takes his revenge against the Uraban man for the slaying of Prester-Marshall Baine and his followers. The retaliatory murder of the diplomat is an atrocity that further inflames the Urabans.
Ignoring his new wife Cliaparia, Omra leads violent raids along the Tierran coast. In Windcatch, as her pregnancy progresses, Adrea misses Criston, who has sailed far away in the Luminara; her brother Ciarlo is training to become the next prester of the village. Everything seems at peace, until Omra and his raiders strike Windcatch, setting fire to the buildings, massacring many of the townspeople, and destroying the small Aidenist kirk. Ciarlo, unable to run with his injured leg, barely escapes and hides. The men are about to kill Adrea, but when Omra sees she is pregnant, he thinks of his own wife Istar who died in childbirth, and he spares her. Omra takes Adrea captive, along with many Tierran children, who are herded aboard the Uraban raiding ships. They sail away, leaving the wounded Windcatch behind. Eventually, they reach Olabar, and Omra tells Adrea that this is her new home.
Meanwhile, voyaging aboard the Luminara, Criston sees many new and strange things. Captain Shay takes him under his wing, showing off the journal in which he sketches the sea serpents he has encountered. Criston also becomes close with PRESTER JERARD, a kindly old priest. He writes his letters to Adrea, seals them with a strand of her hair, and throws the bottles overboard. The ship has been gone for months, seeing no sign of Terravitae, when they encounter a terrible storm—along with the most terrifying sea monster of legend, the Leviathan. The Leviathan attacks and destroys the Luminara.
Criston and Prester Jerard are the only survivors. For days, they drift on a makeshift raft, fighting off sharks. Then a black-and-gold sea serpent devours the prester, but Criston manages to snag it with an iron hook. The enraged beast races through the water, dragging Criston's hodgepodge raft for many leagues before the rope breaks. Fortunately, the serpent has towed Criston back into Tierran shipping lanes, and he is rescued. When he finally makes his way home to Windcatch, desperate to see Adrea, he finds the town recovering from the Uraban raid. Ciarlo reveals that Adrea was either kidnapped or killed; she is long gone and there is no chance of getting her back. A broken man, Criston leaves Windcatch, rejects the sea, and goes up into the mountains to live alone.
Four years later, Aldo na-Curic is an experienced Saedran chartsman and has sailed on many Tierran ships. When his captain ventures south of the Edict Line, however, the ship is surrounded by Uraban war vessels. Aldo, with his rare talent as a chartsman, is captured and taken to Olabar, where Soldan-Shah Imir asks a wise Saedran woman, SEN SHERUFA NA-OA, to convince the young man to serve Uraba. But both Aldo and Sherufa owe their loyalty to the Saedran quest to complete the Map of All Things, and she gives him all of her information about Uraban geography, then secretly helps him escape back to Tierra, where he can share his knowledge.
Since recovering from his burns and murdering his benefactor Asha, Prester Hannes has adopted a new mission: stranded in a foreign land, he vows to harm the enemy as much as possible. Moving like a shadow, he burns churches, poisons wells, and wreaks havoc among the followers of Urec. They are spooked and assume that the Tierrans have sent many spies and saboteurs among them.
Over the years, Omra has kidnapped many Tierran children and—under the guidance of a sinister and mysterious masked figure, the Teacher—has brainwashed and transformed them into zealous assassins and saboteurs, called ra'virs, which he intends to turn loose on Tierra. Adrea is a household slave at the palace, and all this time she has pretended to be unable to speak. She has given birth to Criston's son, SAAN, whom she is allowed to raise; the boy is now almost four, and is being schooled in Uraban ways and the teachings of Urec. Ur-Sikara Lukai informs her that when the boy turns four, Saan will be taken away from her and sent to a special training camp to become a ra'vir. Adrea is panicked, but there is nothing she can do.
She accidentally discovers a plot hatched by Ur-Sikara Lukai and VILLIKI, another wife of Soldan-Shah Imir, to poison Omra, frame Cliaparia, and then set Villiki's good-natured and unambitious son TUKAR (Omra's half-brother) on the throne. Adrea reveals the plot to Omra and, as payment for the information, demands that Saan be kept out of the ra'vir camps and raised in the palace instead. Their scheme exposed, Ur-Sikara Lukai is killed, Villiki is stripped of all possessions and cast out, and Tukar (who had no real part in the plot) is exiled to live at the harsh Gremurr mines. Saan is brought back to Adrea, but the old soldan-shah is broken by the revelation of the murderous scheme, and so he retires, handing over the leadership to Omra.
After saving Omra's life, Adrea is taken into the new soldan-shah's household. Despite the obvious jealousy of Cliaparia, Omra asks Adrea to marry him as well, and in return he promises to raise Saan as his own. Seeing this as the only way to ensure a future for her son, she grudgingly accepts. But a Tierran name will not do for the wife of a soldan-shah, and Omra insists that she change her name to Istar.
Meanwhile, Criston Vora lives in isolation in the mountains, going to other villages only when he needs supplies. Once each year he makes the trip to the seashore, where he casts another letter in a bottle into the sea, clinging to hope that someday, somehow, Adrea might receive them….
Up in Tierra, Mateo undergoes years of military training, including arctic survival with the destrar of Iboria, BROECK. Broeck takes a liking to Mateo, and when his daughter ILRIDA agrees to be the new bride of lonely King Korastine, Mateo escorts her down to Calay. Anjine is thrilled to see Mateo back in the city (they are very fond of each other but cannot admit their feelings), and Korastine is delighted with his new bride, who is fascinated by legends of Holy Joron in Terravitae. As a special gift for Ilrida, the king constructs an Iborian-style kirk so that she can worship as she did in her own land.
Over the years, Omra becomes very fond of Saan and raises him as a true son, despite the boy's Tierran heritage. Adrea/Istar and Cliaparia develop a rivalry as wives: no matter what she tries, Cliaparia can't make Omra love her, and the soldan-shah's true affection is reserved for Istar. He now has three daughters—ADREALA and ISTALA by Istar and CITHARA by Cliaparia, but the soldan-shah still needs a male heir.
Back in Calay King Korastine and Ilrida are very happy together and produce a son, TOMAS. One day, as she prays in the special Iborian kirk that Korastine built for her, Ilrida scratches herself on a rusty nail. The wound becomes infected, and Ilrida dies of tetanus; Korastine is so paralyzed by grief that Princess Anjine shoulders more and more of the burdens of ruling Tierra. Knowing how much Ilrida revered Holy Joron, Korastine announces a quest in her honor: Tierra will build another great exploration ship that will sail off in search of Terravitae. Anjine thinks this is an expensive fool's quest in a time of war, but Korastine takes her to a high tower and shows her a relic that has been kept secret for generations: Aiden's Compass, a magical object that will reveal the location of the lost homeland. Anjine sees that the plan isn't so foolish after all….
At the southern boundary of Uraba, at the edge of the Great Desert, a strange man staggers in from the dunes, speaking no tongue that anyone can understand. The Saedran woman Sen Sherufa eventually learns his language. His name is ASADDAN and he has crossed the Great Desert; his people, the Nunghals, live on the other side of the expanse of dunes. Asaddan becomes a court sensation and convinces Omra to sponsor an expedition so he can return to his side of the desert, using a balloon-borne sand coracle to ride the winds. Saan, now twelve, accompanies him, along with the retired soldan-shah Imir and a reluctant Sherufa (who would rather stay home and read about adventures). The group crosses the desert and is received among the Nunghals. As guests of KHAN JIKARIS, they travel to a large clan gathering on the coast of the southern ocean, a body of water that Sherufa never even guessed existed. From seafaring Nunghals, she obtains maps and begins to suspect that the southern ocean may in fact connect with the coastline of Uraba, far to the north. Sherufa, Imir, and Saan return home with their exciting news.
Prester Hannes continues his depredations against the followers of Urec, leaving a path of death and destruction behind him as he makes his way back to Tierra. He reaches the burned ruins of Ishalem, which have remained uninhabited for more than a dozen years, and he weeps to see what has become of the holy city. Before he can leave the ruins, though, Hannes is captured by a Uraban patrol, and he is sent with other prisoners to work in the Gremurr mines. They do not know he is the man who has caused them so much harm; they just need more slaves. Hannes toils for a long time, always looking for a way to escape, and finally slips away from the mines into the supposedly impassible mountains that lead to Tierra. No man has ever survived the trek, but Hannes is not like any other man. Frostbitten, starving, and near death, he stumbles into a high mountain meadow, where he is rescued by the hermit Criston Vora. Criston nurses him back to health, and then helps the prester make his way to Calay.
As the Iborian Kjelnar constructs Korastine's new Arkship, Destrar Broeck goes out into the northern wastelands to track down and kill the fabled ice dragon, whose horn supposedly has magical properties. Broeck returns to Calay with the shimmering horn, which will be mounted on the prow of the Arkship. Both Broeck and Korastine intend to sail on the vessel, and Aldo na-Curic will be the chartsman. Before the new Arkship can depart, though, ra'virs strike in the night and burn the ship in the harbor. The Tierran dreams are dashed.
Soldan-Shah Omra decides to recapture the barren city of Ishalem for his people and puts together a major assault. His wife Istar gives him a son at last, whom she names Criston, which only increases the jealousy Cliaparia holds toward her. Omra has recently taken a third wife, NAORI, who is also pregnant. The soldan-shah bids them all farewell, and heads off with his armies to conquer Ishalem. His operation works perfectly. Before the Tierran army can respond effectively, Omra destroys the enemy military outposts and kills all the Aidenist pilgrims. He claims the ash-strewn ground in the name of Uraba.
Back in Olabar, Cliaparia schemes to oust Istar, but she fails… which only forces her to try even darker treachery. After Naori gives birth to a baby boy—another heir for the soldan-shah—Cliaparia slips a poisonous sand spider into the crib of Istar's year-old son Criston, and the boy dies. Saan returns from the land of the Nunghals to discover that his mother has been nearly driven mad by the death of the baby, while Cliaparia remains smug. When Istar learns that Cliaparia was the murderer, she does not hesitate. Thinking of nothing but revenge, she goes to the market, where she finds Cliaparia laughing with her ladies-in-waiting. She stabs the hateful woman to death in broad daylight and dumps her body into the harbor, then staggers away in shock, covered in blood. As she wanders through the market stalls, Istar is stunned to discover a merchant selling a letter found sealed in a bottle. One of Criston's letters to her.
Having saved Prester Hannes, Criston at last decides to return to his former life. Over the years living alone in the mountains, he has dabbled with making models of sailing ships, exploring different designs. King Korastine and all of Calay are reeling from the heinous burning of the Arkship, but Criston presents himself to the king with new models and offers his services to create, and captain, a new ship.