The prologue begins many moons in the past. Eight injured cats, including SkyClan's leader, Spiderstar, arrive in SkyClan's gorge. They are greeted by the medicine cat, Brackenheart, and three elders (who were warriors and apprentices when SkyClan was exiled). Despite the protests of the deputy, Honeyleaf, the cats admit that they have been defeated by the rats, and that SkyClan is no more. Several of the cats decide to become kittypets, as the Twolegs have been giving them food, and a couple, including Honeyleaf, decide to travel farther down the gorge and live as rogues. The elders decide to stay in the gorge, and Spiderstar and Brackenheart promise to stay with them until the end. After the cats leave, Spiderstar wearily wonders if a Clan will ever live there again. Brackenheart declares, "This is the leaf-bare of our Clan. Greenleaf will come, but it will bring even greater storms than these. SkyClan will need deeper roots if it is to survive."
The main story opens with a flood surging through the camp. Leafstar watches in horror as she watches her Clanmates get swept away... but then wakes up: it was only a dream. Leafstar goes out and watches her Clan. Since Firestar's Quest, several cats have joined the Clan: Shrewtooth, a nervous black tom; Lichenfur and Tangle, two elders; Waspwhisker and Fallowfern, two loners that have become mates and had kits since joining the Clan. Despite not everybody being in the gorge (Sharpclaw says they never know when the absent cats will come), Leafstar performs a ceremony, giving Bouncepaw, Rockpaw, and Tinypaw the warrior names Bouncefire, Rockshade, and Tinycloud. A little while after, Shrewtooth screeches that there's an invasion, but it's only Ebonyclaw, Billystorm, and Snookpaw, some of the daylight-warriors. Because SkyClan's numbers are so small, Leafstar has allowed kittypets to join the Clan, hunting and patrolling during the day but going to sleep in their Twoleg nests at night. There's a bit of conflict about daylight-warriors, though; the gorge-born warriors consider them to not be "real" warriors, coming only to have fun and leaving whenever there's real work to get done. Those who are descended from the ancient SkyClan - or at least think they are - consider themselves better than the daylight-warriors as well.
That night, Spottedleaf appears in a dream to Leafstar. She shows her a vision of the scene from the prologue, and the part about "deeper roots" is what stands out most to Leafstar; she wonders if it's a prophecy. Echosong reports the next morning that she had the same dream, so the two know that it's important.
A few days later, things aren't much better. Leafstar banishes two of the daylight-warriors, Harveymoon and Macgyver, for a moon for slacking off and being rude to Sharpclaw about it. Sagepaw, when trying to help clean out the dens, ends up slipping off the cliff and falling; he's injured, but not fatally. It turns out that he'd been trying to prove he was descended from ancient SkyClan after being teased that he wasn't. When Leafstar tries to hold a Clan meeting to explain that all cats have an equal claim to being SkyClan members, intruders show up in the gorge. The introduce themselves as Stick, Cora, Shorty, and Coal, explaining that they'd helped Firestar when he was trying to find some cats who needed a home. They wish to learn more about Clan life. Leafstar and Sharpclaw are both suspicious of these newcomers, even though Cora promises that they haven't come to cause the Clan harm.
The next chapter is from Stick's point of view back in the Twolegplace, before he went to SkyClan. Stick's group argues with a different group of cats who had arrived in Twolegplace more recently - Dodge's gang is infringing on Stick's group's hunting time. It ends up with the cats fighting each other; one of Stick's cats, Percy, loses an eye. After the fight, Stick worries about his daughter, Red, as she hasn't arrived home yet.
The day after Stick's group arrived in SkyClan, Leafstar's patrol discovers a pile of Twoleg waste farther along in the gorge, and that it is filled with rats. Stick, having some experience with rats, comes up with a plan to fight them. Six days later, they attack the rats, despite Leafstar's misgivings about not bringing along daylight-warriors (it was thought that, because the attack took place before dawn, none of them would be out of their nests yet). They win, but Waspwhisker is pretty badly injured. Sharpclaw praises the Twolegplace cats, and Leafstar wonders what their intentions are.
It then jumps back to Stick's point of view. While wandering the Twolegplace looking for food, Stick comes across two of Dodge's cats hunting a rabbit - but it's not a wild rabbit, it's a Twoleg pet. They hurt the rabbit and frame him for it. Stick flees from the angry Twoleg and confronts them. The two comment offhand that they've seen Red around a lot lately, and that maybe Stick will find her fur next. Stick warns them to not make threats they can't keep, and Misha purrs that they're not threats, they're promises.
The full moon comes not long after the battle. The Clan discusses the recent battle and other concerns. After the Gathering, Leafstar stays behind with Echosong and Sharpclaw. Echosong has shared her desire to make Frecklepaw her apprentice, but Sharpclaw isn't very happy with the idea, as Frecklepaw is a daylight-warrior and he does not think it wise to have a medicine cat that could be shut inside when a warrior is dying. The next day, Snookpaw falls in the river. It's cold and both he and Leafstar (who pulled him out) are exhausted, but rather than letting Echosong check him, he insists upon returning to his Twolegs.
Leafstar continues to wonder what exactly Stick and his group wants. Cora seems to think they aren't staying in the gorge, but she doesn't really talk about it to Leafstar. Sharpclaw suggests that it's time to make Stick and his cats warriors. Leafstar reflects on how helpful they've been, and agrees. During the ceremony, Stick interrupts twice - one time asking that they keep their own names - and several cats aren't happy about them becoming warriors, since they haven't had any training. That night, Leafstar dreams of StarClan - they're having a party to celebrate SkyClan's return. Spottedleaf urges Leafstar to seize the moment and not to worry about the future. The next day, Leafstar and Billystorm check on Snookpaw, who hasn't returned to the gorge since falling in the river. It turns out that he'd gotten sick and is just recovering at home. A patrol comes across a loner who clearly has SkyClan ancestry, but he flees from them.
We see Stick's POV again. After arguing a bit with Red, his daughter runs off, with one of Dodge's cats right behind her. Before Stick can follow, he's distracted by Twolegs attacking the alley. He follows his daughter as quickly as he can, and discovers her with Dodge's cat Harley, a young tom. Harley promises Stick that he'd never let anything happen to Red. Stick doesn't believe him, and Red tries to prove it by saying that Harley knew about the attack and warned her away - she hadn't told Stick because he'd never believe a warning if it came from one of Dodge's gang. Stick declares that she's no daughter of his, and leaves. He returns to his alley to find that the Twolegs have taken away Percy.
The main story returns a few days after Leafstar had made the other cats warriors. Upon hearing Ebonyclaw's concerns for Shrewtooth, Leafstar patrols with the nervous warrior, and it ends with him being spooked at a Twoleg nest - the nest where Petalnose and her kits had been kept. They decide that the Twoleg is a danger to the Clan and decide to attack him. They had planned to do it the day afterward, but that night Sharpclaw wakes Leafstar and tells her that they have perfect weather tonight and they can't guarantee they would the next day. Leafstar relucantly agrees, though she knows that they daylight-warriors won't be very happy that they were left out. They successfully frighten him enough so that he won't harm any cats again. The fight bonded the SkyClan warriors and everyone's cheerful... until the next day, when the daylight-warriors arrive. An argument breaks out, and even trying to allow daylight-warriors and gorge warriors to patrol together doesn't work, so Leafstar patrols with a group of daylight-warriors. Echosong asks to speak to her, and Leafstar shares her fear that the whole daylight-warrior thing isn't working. Echosong just warns her to beware of her own feelings, and leaves without any more explanation.
Stick's point of view picks up right where it left off. He decides that his gang should find where Dodge's group lives, so they split up - he decides to follow Red and Harley's scents, and he's joined by Shorty. Shorty persuades Stick to talk to his ex-mate, Velvet, Red's mother, to see if she might be able to help with Red.
A few days after the arguments about the daylight-warriors, tensions have eased a bit, but they're still not completely gone. The loner they had seen before, Egg, decides he wants to join the Clan after all, but he refuses his apprentice name, preferring instead to be known as "Egg", just as Stick and his friends had kept their own names. She discovers, however, that Sharpclaw had convinced him to join the Clan by saying that he wouldn't be safe alone since a fox moved in. Leafstar wonders, not for the first time, what exactly Sharpclaw is keeping secret. Echosong and Leafstar talk again, about how Echosong wants Frecklepaw as an apprentice, and Echosong points out how Leafstar is getting very close to Billystorm. She reminds Leafstar that the warrior code says a leader cannot have kits. When Leafstar gets back to the camp, Billystorm invites her to the Twolegplace to keep an eye out for Sharpclaw and Stick's mysterious patrols. Remembering what Echosong had told her earlier, she declines, adding that she doesn't have any reason to believe that Sharpclaw is doing anything wrong, and Billystorm accuses her of being prejudiced against daylight-warriors.
Three days afterward, the Clan hears a strange noise. It turns out to be an injured female Twoleg kit, who has fallen into the gorge and broken her leg. Leafstar decides that SkyClan will help the Twoleg. Snookpaw recognizes the scents on the Twoleg and knows where she lives. They find the nest but can't get the girl's parents to understand them (they even get a flowerpot thrown at them), so they get the idea to make a trail of items from the young Twoleg's backpack. The parents follow the trail and find their daughter, and they get help to rescue her. Leafstar decides to honor Snookpaw's actions the next day by making him a warrior. She gives him the name of Snookthorn, but after the ceremony, he tells his Clanmates that he hated seeing the Twolegs angry at him yesterday, and he doesn't want to be an enemy of Twolegs, and he leaves the Clan. Leafstar wakes up in the middle of that night to see Sharpclaw leading a patrol out of the camp. She watches them train and eventually confronts them. Stick, Shorty, and Cora decide that they want to tell SkyClan the truth: they came not to join the Clan, but because they needed help.
It flashes back to Stick's point of view. He visits his ex-mate, Velvet, a kittypet, asking her if she can make Red see sense. Velvet tells him that Red knows her own mind, and that Stick should accept the fact that she's fallen in love with a cat that lives by a different set of rules - after all, he once did the same. She advises him to not fight over Red, and let her follow her heart, or else Red will end up hating Stick. After the talk, Stick is joined by Shorty, and the two spy on Dodge's camp, where they see Red being welcomed into the group. Stick, thinking Red is telling them information about his gang, wants to attack, but Shorty points out that even their whole group isn't enough. He remembers Firestar and Sandstorm, and the two decide to look for Clan cats.
Leafstar decides she needs to think for a while after Stick finishes telling his story. She goes to her den and dreams of Skywatcher and another SkyClan ancestor, who give her opposing viewpoints on the situation. When she wakes up, she patrols with some of her cats, and they come across a bee's nest. Frecklepaw climbs the tree because honey is useful in the medicine den, and when the branch she's on breaks, the bees swarm and attack. They rush back to the gorge; fortunately, most cats are out on patrol and the kits are in the nursery, so Leafstar's patrol and the remaining cats in the gorge dive into the river until the bees fly away. Echosong tells Leafstar that it's a sign - there's some sort of trouble that, if SkyClan doesn't act, will make its way into the gorge. There is a battle somewhere that they can fight before it comes to their camp. Leafstar realizes then that she must help Stick and his friends.
Leafstar and her cats leave the next day. Leafstar has a dream while they are traveling; again, she hears the "deeper roots" line. They arrive in the Twolegplace on the third day. Stick's friends greet the cats they'd left behind in the city, and it turns out that Percy has been returned to the streets; the Twolegs only took him away to neuter him. They decide to attack that night. During the battle, Leafstar and a few of her Clanmates help a queen get her kits to safety. Misha attacks Leafstar and takes one of her nine lives, even as she carries one of the kits. When Leafstar wakes up, Red and Harley arrive back in Dodge's camp (they'd left together shortly before the attack). Red confronts her father, who is fighting Dodge. He claims that they've stolen her away, and she protests that no, she came because of her love for Harley. Stick is blind to this and claims that it's not love; Harley must have tricked her somehow. He leaps at Harley to deal him a killing blow, and Red jumps in his way, taking the blow that was meant for her mate. Stick is horrified at what he has done, and Dodge stands up for Harley. The two are about to resume their fight when Sharpclaw stops them. The SkyClan cats speak to them, soothing both parties, and when they agree that no more fighting is necessary, SkyClan leaves.
SkyClan spends the next few days traveling home. On the way, Leafstar tells Sharpclaw that she's willing to fight to keep her leadership position, but he assures her that he has no desire to usurp her; he had only been challenging her to help build faith in herself. Leafstar decides that regular Clan cats will respect the daylight-warriors' lifestyle, and that Frecklepaw will be apprenticed to Echosong. She sets down new rules: Visitors will be accepted, but they must hunt every day, and will not be allowed to train to learn fighting skills until they have stayed with the Clan for a moon, and they must leave if they bring danger to the gorge. Leafstar realizes she's expanding the warrior code to fit SkyClan, and she believes that this is what was meant by "deeper roots". She decides that if she has the power to choose the destiny of the Clan, she also has the power to choose her own destiny. She goes over to Billystorm, and the book ends with her telling him, "Will you walk with me a while? We need to talk..."
The manga at the back is from Rabbitpaw's point of view (one of Fallowfern's kits, who had been three moons old during the main part of the story, and is now nearing the end of his apprenticeship). During his final assessment, he catches a squirrel on the ground instead of climbing a tree to get a bird, because he is scared of climbing. He fears that he won't be allowed to be a warrior, and Leafstar herself is uncertain since that's always been an important part of SkyClan's skills. When they get back to camp, they run into Harveymoon and Macgyver, who had been fleeing from a couple dogs who have been trouble in the Twolegplace. Leafstar decides to lead a patrol that night. Rabbitpaw wants to come along, and Leafstar agrees. A kittypet tells them where they might find the dogs, and the SkyClan patrol splits up - Sharpclaw takes a group to where the dogs supposedly live, and Leafstar and Rabbitpaw wait to ambush any dogs that get past Sharpclaw's group. Leafstar and Rabbitpaw hear barking from somewhere near them, and they go to warn Sharpclaw's group, but they end up running into a dead end alley. The kittypet appears in a tree on the other side of the fence and sneers that they're not wanted there. Leafstar and Rabbitpaw hide in a trash can, which the dogs knock over in a way that they can't quite get at the cats, but the cats can still get out. One of Leafstar's legs is injured, however. Rabbitpaw goes to get Sharpclaw's group. Meanwhile, however, they have found Billystorm, who tells them the kittypet must have lied, and they go to help Leafstar and Rabbitpaw. As Rabbitpaw runs out, they attack the dogs, and he helps fight. After they chase them away, Frecklepaw - now Frecklewish - checks on Leafstar's leg. When they arrive back at the gorge, Leafstar holds a warrior ceremony. She names Fallowfern's kits Nettlesplash, Creekfeather, Plumwillow, and Rabbitleap, who is pleased he is made a warrior. Leafstar tells him she's proud of him.
Tropes appearing in this book:
- Alertness Blink: In the manga at the end, Sharpclaw has an exclamation point appear above his head when the patrol encounters Billystorm.
- Bad People Abuse Animals: The perpetually nervous Shrewtooth reveals that he is so jumpy because he used to be owned by a cruel Twoleg who had once also owned Petalnose and her kits. SkyClan attacks the man to try to teach him not to mistreat any more of his pets.
- But Now I Must Go: Snookthorn leaves the Clan after seeing how Twolegs dislike feral cats; he'd rather return to his kittypet life than feel that way ever again.
- Career Versus Man: Clan tradition is that female leaders and deputies cannot have kits since it might get too in the way of their responsibilities to the Clan. Leafstar spends much of the book thinking about how unfair this is after she realizes she has feelings for Billystorm, and by the end of the book she decides that she doesn't care and that it's fine for SkyClan, since the warrior code states "The word of the Clan leader is the warrior code".
- Chew Toy: Percy. Most of Stick's group gets away with just wallowing in Dodge's incredibly vague Offstage Villainy, but Percy is singled out for both having his eye ripped out and getting fixed. In fact, he doesn't have any role in the story other than having horrible things happen to him.
- Confused Question Mark: In the manga at the end, a dog gets one when hearing Leafstar and Rabbitpaw's voices from inside a trash can.
- Cultural Rebel: Stick and his friends choose not to take Clan names, and later Egg chooses not to as well, which annoys Leafstar because it feels like they're rejecting being part of the Clan.
- A Day in the Limelight:
- This novel and the SkyClan and the Stranger manga are Leafstar's time to shine in her POV.
- Minor character Stick gets several flashback chapters from his POV.
- Dark Is Evil: The main antagonist, Dodge, is a dark brown tabby.
- Did You Just Punch Out Cthulhu?: In SkyClan's Destiny, SkyClan takes it upon themselves to defeat the Twoleg who keeps abusing cats. Also averted when, in the same book, the cats save a Twoleg kit with a broken leg.
- Distant Prologue: The prologue takes place several generations before the main story of the book; long enough that SkyClan had long since been disbanded and been forgotten by the modern Clans before being re-formed in the previous book.
- Dream Intro: The first chapter begins with Leafstar having a nightmare about the camp flooding.
- Edible Theme Naming: The Erins must have been hungry when they wrote this book, because several of the new characters are named after food: Egg, Onion, Nutmeg, and you could even count Velvet if you think of red velvet.
- Exact Words: The warrior code rule "The word of the Clan leader is the warrior code" was chosen so that cats obey the decisions of their Clan leader (originally suggested after a deputy undermined their leader's authority in front of the other Clans). Leafstar uses it to decide that the forest Clans' rules don't totally fit SkyClan and that she can make her own amendments to the warrior code.
- Eye Scream: Percy gets an eye ripped out.
- Flashback B-Plot: Rather uniquely for the series, this book works this way. The current-day story of SkyClan is interspersed with chapters from Stick's point of view, back before he left the city, some time earlier than the main events of the book.
- Glowing Flora: The Whispering Cave in SkyClan's gorge has phosphorescent moss growing inside.
- Grumpy Old Man: The elder Tangle is portrayed this way.
- Is That a Threat?: Stick responds to one:Skipper: "I've seen Red around a lot lately. Next time, it might be a tuft of her fur that's left beside a dead Twoleg pet."Stick: "Leave Red out of this. And don't make threats you can't keep."Misha: "Oh, they're not threats. They're promises."
- Nervous Wreck: Shrewtooth, until SkyClan dealt with the Twoleg that made him that way.
- Not a Morning Person: Shorty. He complains that he can't get used to early mornings and Leafstar tells him that he will sooner or later.
- A Pet into the Wild: Several of the new SkyClan cats were kittypets who left their homes to join the Clan.
- Pets Versus Strays: There's conflict in the book between "daylight warriors" - kittypets who help out the Clan during the daytime but return to their owners' homes at night - and full-time SkyClanners.
- Ruler Protagonist: Leafstar struggles with the possibility that her deputy might be trying to undermine her, as well as with the strictness of the Clans' warrior code; the book ends with her deciding that the law "The word of the Clan leader is the warrior code" means that rather than having to stick strictly to all the rules of the code, she has the right to be flexible and change the code for what works for her own Clan.
- Scary Stinging Swarm: One scene involves the cats accidentally knocking down a bees' nest, and getting attacked by the resulting swarm.
- Series Continuity Error: In Firestar's Quest, Mousefang was a warrior when SkyClan left the forest. In the prologue in SkyClan's Destiny, she says that she was a kit when they left.
- Shout-Out: Macgyver is named after the television show of the same name, as Vicky is a fan.
- Signature Item Clue: A young girl falls into SkyClan's gorge and is injured. Since the cats are unable to communicate with humans, they get the idea to take items out of her backpack and create a trail to where she is. The girl's parents recognize their daughter's belongings, and follow the trail until she is found.
- Spoiler Title: Both subverts and plays this straight.
- It plays it straight for those who have not read Firestar's Quest, spoiling the fact that there's a long-lost Clan out there.
- It subverts this by being named after the Clan itself, rather than after the viewpoint character, thus avoiding spoiling which member of the newly founded SkyClan becomes leader at the end of Firestar's Quest.
- Star-Crossed Lovers: Red and Harley are in love, but are from enemy factions and their families do not support their romance, especially Red's father Stick. In the end, Red gives her life to save Harley from her attacking father.
- Supporting Protagonist: Leafstar is the perspective character, however, Stick is the main character and the story centers around his struggles with the evil Dodge.
- Swarm of Rats: The rats from Firestar's Quest are back to antagonize SkyClan again.
- Taking the Bullet: Red does this for Harley, jumping in the way when Stick goes for Harley's throat.
- Team Title: SkyClan's Destiny.
- Timmy in a Well: A young girl falls into the gorge, and the cats know that it'll mean that other humans will be looking for her - not to mention that half the Clan are or were kittypets that don't want a human to be hurt. When initial attempts at leading other humans to the gorge fails, they get various items out of the girl's backpack and create a trail leading to the gorge.
- Title Drop: Toward the end of the book, Leafstar says, "SkyClan's destiny is that we will never live in isolation from other cats."
- Vagueness Is Coming: Many prophecies in the series vaguely foretell destruction and danger without actually managing to tell the Clans what exactly is coming. This includes the one in this book: "Greenleaf will come, but it will bring even greater storms than these. SkyClan will need deeper roots if it is to survive."'
- What Happened to the Mouse?: After joining SkyClan in this book, Egg just disappears from the books, never showing up or even being mentioned again.
- Why Did It Have to Be Snakes?: SkyClan and rats, due to the events of Firestar's Quest.
- You Dirty Rat!: A large group of rats was responsible for ending the original SkyClan. They're determined to make sure it doesn't stay rebuilt.
