Naia is on patrol in the Swamp of Sog when she sees a Gelfling of the Vapra Clan approaching. She informs her mother, Maudra Laesid, of the newcomer and goes to greet her. Naia goes to greet the stranger, who introduces herself as Tavra, a soldier sent by All-Maudra Mayrin. Naia's father, Bellanji, joins them and invites Tavra to attend the evening feast.
During the feast, Naia accidentally dreamfasts with Tavra and learns that the All-Maudra has told Tavra to find Naia's brother Gurjin and another Gelfling named Rian. Naia's parents question Tavra after the feast and she tells them that Gurjin and Rian have been accused of treason by the Skeksis and have gone on the run as fugitives. It is decided that Naia and Bellanji will accompany Tavra to Ha'rar and defend Gurjin's good name.
The following morning, Naia, Tavra and Bellanji set out on their journey, but as they reach the edge of the swamp they are attacked by a nebrie that is infected by the Darkening. During the fight that ensues, Naia finds violet crystal veins beneath the water and Tavra and Bellanji are both badly wounded. Naia dreamfasts with the nebrie and feels its pain before it drops dead. Tavra and Bellanji are too injured to carry on and elect to go back and have their wounds treated while Naia continues the journey with only her pet muski Neech for company.
Naia leaves Sog for the first time in her life and find the terrain to be hostile. She fashions a pair of sandals out of bark, but they prove ineffective. She soon encounters a podling, who gives her directions to Sami Thicket, home of the Spriton Clan. She meets with Maudra Mera, who allows her to stay for the night. Later that evening, SkekOk the Scroll Keeper and SkekLach the Census Taker arrive to take a census of everyone in Sami Thicket. As part of the entertainment, Mera's adoptive son Kylan sings a song about the Gelfling folk hero Jarra-Jen and his encounter with the Hunter, a nightmarish figure of legend whom Kylan claims killed his birth parents. The Skeksis do not believe him, stating that the Hunter is merely a myth.
The next morning, Naia prepares to leave and Mera gives her some packed food, a skin of water and nebrie-skinned shoes to aid her on her journey. As she makes to continue her journey, Naia sees Kylan being bullied by other young Spritons for his inability to throw a bola. She defends him and upstages the bullies with her own bola-throwing skills. Kylan catches up to her and tells her that he is heading for Stone-in-the-Wood and asks to accompany her that far. She initially refuses, not wanting to be burdened with ensuring his safety, but reluctantly agrees when he insists that he makes up for his lack of combat skills with his song-telling and cooking abilities.
Naia and Kylan find an abandoned podling dwelling, where the violet crystal veins have spread. They are attacked by a Darkened ruffnaw, which Naia dreamfasts with to feel its pain. Kylan scares it away be mimicking the call of a hollerbat. The two Gelfling dreamfast, with Naia showing Kylan her encounter with the Darkened nebrie and him showing her the night that the Hunter took his parents.
Naia and Kylan enter the Dark Wood but are soon separated from each other. Naia is visited by phantom-like apparitions of Gurjin, Tavra and her loved ones who attempt to break her spirit by telling her that Gurjin is a traitor and she cannot save him. She escapes from them and reunites with Kylan, who has had similar visions. Realizing that the whole forest is infected, they make their way to the Olyeka-Staba, the Cradle-Tree. Naia dreamfasts with it and heals the forest of the Darkening. A nearby tree then breaks apart to reveal UrVa the Archer.
UrVa invites Naia and Kylan to his home and provides them with food, shelter and beds to sleep in. During their stay, Kylan becomes engrossed by some carvings that UrVa has made regarding the Great Conjunction, but UrVa is vague regarding their meaning. He leads them to the Black River and informs them that someone is searching for them.
As they make their way down the river, Tavra arrives on a Landstrider and tells them that she has been sent to tell Naia to return to the Swamp of Sog. Naia reluctantly promises that she will, but once Tavra is gone she resolves to go to the Castle of the Crystal, deducing that Gurjin is being kept there. Kylan refuses to accompany her, believing it to be reckless and dangerous. As she continues through the forest and nears the Castle, she is cornered by the Hunter, but manages to drive him off with the help of Neech.
Once she reaches the Castle, Naia finds Tavra at the front gate. They are greeted by SkekSil the Chamberlain, who reveals that Tavra is in fact All-Maudra Mayrin's daughter. Tavra tells him that Naia is her retainer and he brings them before his fellow Skeksis. Tavra tells them that Gurjin and Rian have not yet been found and SkekSo the Emperor orders her to continue the search. Tavra tells Naia to go and prepare her quarters, but Tavra gets a sense that Naia knows something is very wrong.
As she makes her way through the corridors, Naia is disturbed to see that the Gelfling guards and Podling servants are very pale and lifeless. She sneaks into the Crystal Chamber and discovers that the Crystal has been cracked and corrupted. Through it she sees Tavra questioning the Skeksis about whether they have betrayed the other species of Thra and SkekSo confirms her suspicions. SkekSil grabs her and the other Skeksis join in and overrun her, carrying her to the Chamber of Life. Naia asks the Crystal to show her where Gurjin is and it reveals that he is in one of the Castle's upper turrets.
Naia makes her way upwards and Neech leads her to an area filled with cells and disappears. She finds several pale and lifeless Gelfling in the cell and frees Gurjin from a crate. She attempts to help him out of their but is confronted by SkekMal, who reveals that he is the Hunter and that Naia has been lured to the castle as the Skeksis planned to drian the twins together. He presents Tavra, who has been drained of some of her essence and tells them to escape and warn the others before SkekMal knocks her out. Naia and Gurjin escape by jumping out of the window and into the moat below, with Naia gliding them to safety as she finally sprouts her wings.
Kylan helps Naia and Gurjin as they reach land, but SkekMal gives chase and closes in. Gurjin dreamfasts with Naia and shows her a memory in which he learns from Rian that SkekTek the Scientist killed their friend Mira by draining her of her essence. They stole the vial to prove the Skeksis' crimes to the All-Maudra, but as they fled the Castle Gurjin allowed himself to be caught be SkekUng the General in order to allow Rian to escape. Once they leave the dreamfast, SkekMal attacks and Naia notices that he has a scar on his hand identical to UrVa's and deduces that they are connected. She hesitates when she has a chance to kill SkekMal, believing that it will also kill UrVa.
Kylan buys them some time by throwing a rock at SkekMal's head and sending him into a frenzy. As they flee through the forest, they know they cannot escape him and Gurjin stays behind to distract him while Naia and Kulan escape on the Landstrider. Naia later awakes in Stone-in-the-Wood, where she is reunited with Neech and Kylan informs her that Rian is there and he plans to meet with him later. Hoping to honor the sacrifices of Gurjin and Tavra, Naia chooses not to return home until they are avenged.