The novel follows the ongoing quest of Morgaine, a determined and enigmatic woman, and her reluctant warrior companion, Nhi Vanye i Chya, as they traverse different worlds to close the Gates—ancient constructs capable of catastrophic destruction when misused.

Mija Jherun, a fey seventeen-year-old peasant woman, lives in a world inexorably being overwhelmed by the sea.

One day, after looting a barrow, the tomb of a young warrior-king, she is chased by an armored man on horseback back to her village.

He breaks into the poor home she shares with her family, helps himself to some food, and asks if anyone has seen a pale woman on a grey horse.

After repulsing an attack by the men of the village, he departs for Shiuan, a richer land ruled by the khal, another race that is enough like humans to successfully interbreed.

They inform her that Chya Roh's body had been taken over by an evil creature who had extended his life countless times by this means.

They become separated when Vanye is knocked off his horse by an uprooted tree carried by the rapidly rising, onrushing water.

Vanye is left behind, a prisoner of Hetharu's brother Kithan, but is rescued by Morgaine and an army she has recruited from Jherun's people and their neighbors, the marshlanders.