The book opens with Percy Jackson attending freshman orientation at Goode High School, where he sees Rachel Elizabeth Dare, who helps him to recognize and fight two empousai disguised as cheerleaders, Tammi and Kelli. Percy is forced to flee to Camp Half-Blood, while Rachel stays behind. On the way, Percy runs into Annabeth, who is annoyed to find him in the company of a mortal girl. When they reach camp, Percy learnsGrover is in trouble from the Council of Cloven Elders for not having made progress finding the god Pan after claiming he felt Pan's presence in New Mexico that winter. Percy also encounters a middle-aged demigod named Quintus, who is the new sword instructor of Camp Half-Blood.Chiron describes the man as "hard to read", a description Percy agrees with.

During a competition organized by Quintus, Annabeth and Percy accidentally find an entrance into the Labyrinth. Chiron holds a council of war, and it is revealed that Annabeth and Clarisse have been working together under the suspicion that Luke plans to use this door as an invasion route. To do so, he will use Princess Ariadne’s magical string, which is assumed to be in the possession of the ancient inventor Daedalus. Annabeth is given leadership of the quest to stop him, and chooses Grover, Percy, and Tyson to accompany her. Chiron warns that three heroes is the traditional number for a quest, but Annabeth is shaken by her prophecy and insists. That night, Percy receives a collect Iris-message and learns that Nico plans to bring back his late sister by exchanging her soul for one who has cheated death. Percy fears Nico will come after him.

The next morning, the four start the quest. After a rattling run-in with the minor god Janus, the questers encounter Hera, who offers to grant the questers a single wish. Annabeth wishes for a way to navigate the Labyrinth, but Hera tells her Percy already knows how. He has no idea what she means, and so the quest continues. Between their adventures, Percy also suffers from frequent nightmares about Daedalus, the Labyrinth, and King Minos, who is now "living" as a ghost advisor to Nico di Angelo. The quartet encounters the monster Kampê and her prisoner Briares; visits the ranch of Geryon, where they find Nico and commune with the deceased Bianca di Angelo; and meet with Hephestus, after which they part ways. Tyson and Grover go to search for Pan, and Annabeth and Percy go to Mount St. Helens. At Hephaestus's mountain forge, Percy confronts some telkhines (who are reforging what is later learned to be Kronos's scythe) and is almost killed, but triggers an earthquake that shoots him out of the volcano.

When Percy awakens after the eruption he caused, he finds himself on the island of Ogygia, inhabited by Calypso, who is revealed to be a daughter of the Titan Atlas. Calypso tells Percy she is cursed to fall in love with heroes the The Fates crash-land on her island, even though each of them must leave. After a visit from Hephaestus, Percy realizes that he must return home. When he finally returns to the mortal world, Percy finds the campers burning his shroud, believing he is dead. After emotional visits with Chiron, Annabeth, and his mother, Percy and Annabeth go to Manhattan to find Rachel Dare, who, being clear-sighted, is able to see the path through the Labyrinth. They are captured by Luke Castellan’s minions and Percy must fightAntaeus. After sparing the life of the demigod Ethan Nakamura, Percy kills the giant and escapes with the help of Quintus's ice-whistle, though he later learns that his killing Antaeus eliminated the last obstacle to Luke's conquest of the camp.

They eventually reach Daedalus’s workshop, where Quintus shows up and reveals that he is actually the ancient inventor, now a living automaton. Daedalus informs them that he scouted out Camp Half-Blood and, believing they could never withstand a Titan assault, consented to give Luke Ariadne's string as part of a deal with the Titans. Suddenly they are discovered by part of Luke’s army, Kelli and King Minos in the lead, with Nico di Angelo in chains. The questers learn Minos had been helping Nico find Daedalus so the inventor's soul could be exchanged to bring back the old king of Crete, not the late Bianca. The betrayed Daedalus and Nico fight with Annabeth and Percy to defeat the Titans, and the four teenagers escape while the inventor remains in the maze with his hellhound.

The quartet later discover the Titan fortress at Mount Othrys, where they learn that Luke has been somehow possessed by Kronos; Ethan Nakamura joins the Titans; and Nico di Angelo is forced to reveal his powers to stop Kronos. They run until they encounter Grover and Tyson, who are still searching for Pan. They follow a tunnel until they come the old god's resting place. Pan speaks to each of them, Nico excluded, and passes his spirit into each person present.

The group heads back to Camp Half-Blood, minus Rachel, and prepares to fight. The enemy army floods out of the Labyrinth, led by Kampê. Daedalus arrives as the tide begins to turn in the Titans' favor, bringing Mrs. O’Leary and a giant Briares. Briares kills Kampe, Grover rescues Camp Half-Blood by causing a Panic, and the remaining campers drive the enemy into a retreat. Nico helps Daedalus to pass on and thus destroy the Labyrinth, which is tied to his life force; the inventor gives Annabeth a laptop he salvaged from his workshop and leaves Mrs. O'Leary in the care of Percy. After a memorial service for the dead campers and Grover being banished by the Council of Elders for blasphemy, Percy leaves camp for the school year.

On his fifteenth birthday at the summer's end, Percy receives a visit from his father. Poseidon tells Percy of evil at work with Kronos now in Luke's body, and also gives him a sand dollar, admonishing him to “spend it wisely”. Nico later appears to tell him the secret to defeating Luke once and for all.[