In the prologue, a Clan of cats called Thunderclan battling against a rival Clan, RiverClan, at a place the cats call Sunningrocks. A cat named Redtail, ThunderClan's deputy, soon realizes that ThunderClan is so outnumbered that they have to retreat. Later, Spottedleaf, the medicine cat of ThunderClan, receives a prophecy from StarClan, the cats' "heaven", stating to Bluestar, ThunderClan's leader, that "Fire alone can save our Clan.".

Into the Wild starts out with a "kittypet" (Clan cats' name for housecats) named Rusty. Rusty is wandering off into the woods when he is stumbled upon by a feral cat named Graypaw. He is a ThunderClan apprentice. Unknown to the two young cats, two warriors from ThunderClan watch them -Lionheart a golden- brown tabby male and Graypaw's mentor, and Bluestar, a blue-gray tabby female who leads the Clan. After they watch Rusty and Graypaw fight and make up, Bluestar offers Rusty a chance to join their Clan of feral cats and train as an apprentice. Rusty goes home to think it over, and then meets Lionheart and another ThunderClan cat, named Whitestorm, in the woods. Rusty then tells them that he accepts Bluestar's offer. Rusty then travels to the ThunderClan camp (the cat's home) and fights Longtail (a prejudiced young warrior of ThunderClan). In a battle of honor, and Rusty splits Longtail's ear and Rusty's collar snaps off. This is taken as an omen from the cats' StarClan that Rusty is meant to be in their Clan. Rusty is then given his new Clan name Firepaw, because of the way his flame-colored coat shines in the sunlight. However, Firepaw soon learns that kittypets are thought to be soft and useless to most Clan-born cats and Firepaw is a cat who did not have "warrior blood" in his veins at all but he is slowly able to adjust to his new life.

Firepaw grows up fast and trains hard to become a full, respected warrior and member of the Clan. Firepaw's natural curiosity is also aroused when he finds himself becoming suspicious of the Clan member Tigerclaw when he is appointed deputy of ThunderClan. This was suspicious because the original deputy, Redtail, had been killed in battle by Oakheart (the deputy of RiverClan). A while after Lionheart becomes deputy, Lionheart is killed in battle as well, and then Tigerclaw becomes the new deputy under very unusual circumstances. Ravenpaw, another ThunderClan apprentice and witness to a murder, tells Firepaw that it was Tigerclaw, not Oakheart who actually killed the former ThunderClan deputy, Redtail. But Tigerclaw makes sure that no cat trusts Ravenpaw, giving Firepaw the motive to take Ravenpaw to a different home. Tigerclaw taunts Firepaw on a regular basis, but Firepaw soon grows used to it.

In the midst of this, Spottedleaf, the medicine cat of ThunderClan, is killed in an attack from a merciless death blow by Clawface of ShadowClan, another one of the four Clans in the forest. During this attack, some of the kits from ThunderClan go missing. Tigerclaw immediately blames Yellowfang, the new ThunderClan medicine cat, because she was taken into the Clan from ShadowClan, ThunderClan's enemy. Yellowfang was also not present after the battle, therefore making Tigerclaw and the rest of the Clan suspicious of her. Bluestar intervenes and said that there was no proof that she did anything, and does not blame her for anything. Yellowfang, whom Firepaw found, has grown to become friends after Firepaw had to take care of her as a punishment for disobeying the warrior code. Many cats in ThunderClan distrusted Yellowfang both because of her former Clan, and also because of a warning given at a Gathering (a meeting of the four Clans where they discuss the needs of the Clans). This warning given by Brokenstar, ShadowClan's leader, described Yellowfang whom ShadowClan had driven from their Clan. He warned that no other Clan should take her in and that they should watch their kits closely, because he blamed her for killing the two kits Brokenstar himself had actually killed. Firepaw is determined to prove Yellowfang innocent of the accusation that she had been stealing kits and rescue the missing kits. Firepaw and Graypaw, determined to prove Yellowfang's innocence, manage to find kits that went missing from the Clan, rescue them from ShadowClan, and drive the real kit snatcher, Brokenstar, from his position as ShadowClan leader. Brokenstar had intended to train the tiny kits early so that he could have more warriors for his Clan; Firepaw's success prevents this from happening. They then drive off Brokenstar. After their adventure, Firepaw and Graypaw are promoted to ThunderClan warriors, and receive warrior names - Fireheart and Graystripe. The story ends as the two new warriors begin their traditional silent vigil until dawn.