Takes place 1 year after the events of Star Fox Adventures and 9 years after the events of Star Fox 64.
After the death of his uncle Andross, Andrew Oikonny assumes leadership of the planet Venom's remaining troops and begins a rebellion. General Pepper orders an attack on Oikonny's forces, hiring the Star Fox team to assist the Cornerian Army. The Star Fox team consists of Fox, Falco, Slippy, and Krystal (from Star Fox Adventures) with Peppy providing tactical support with ROB 64 from the Great Fox, their mothership.
During the battle, Oikonny's flagship is destroyed by an insectoid creature, which attacks the Star Fox team. After Fox destroys the creature, he recovers its damaged Core Memory unit and turns it over to Beltino, Slippy’s father, for research. Beltino explains the creature is a member of a race of robotic insectoids called Aparoids, one of which ravaged the Cornerian fleet 17 years prior. Fearing an invasion, Beltino asks Star Fox to recover an undamaged Core Memory so that they might find a way to stop the Aparoids.
Lured by a false distress signal, the Star Fox team are deceived by Pigma, who tricks them into destroying a giant Aparoid so he can steal its Core Memory and sell it on the black market. Wishing to find Pigma, the team attack the base of his former cohorts, Star Wolf, which consists of Wolf, Leon, and new member Panther. Panther reveals Pigma’s hideout location. However, by the time Team Star Fox arrive to Pigma's hideaway, he has already been infected by the Aparoids and they are forced to kill him. The Memory Unit Pigma had stolen is then sent to Beltino for analysis.
Star Fox prevent an Aparoid assault on Sauria with Fox and Krystal reuniting with Tricky for a brief time. Meanwhile, Corneria is left nearly defenseless, with the Aparoids breaching the planet and infecting General Pepper. The team returns to contain the threat, aided by the unexpected arrival of Star Wolf, who seek to eliminate their common enemy. They defeat an infected General Pepper.
Beltino uses the Core Memory to locate the Aparoid Homeworld, and discovers their vulnerability to apoptosis. He creates a program which, if fired into the Aparoid Queen, will force all Aparoids to self-destruct. Star Fox and Star Wolf travel to the Aparoid Homeworld, only to discover the planet's core is blocked by a regenerative shield.
With the Great Fox becoming infected, Peppy and ROB crash it into the shield to create an opening for the two teams to enter. While Star Wolf takes care of the remaining Aparoid forces, Fox and his allies reach the planet's core. The Aparoid Queen attempts to use the voices of Peppy, Pepper, Pigma and James McCloud to deceive them into joining her, but the team is undeterred. After a long battle, Fox launches the self-destruct program into the Queen, but she resists it and attempts to escape to create an antibody. The team deals the final blow to the Queen, killing her and causing the self-destruction of the planet and all the Aparoids. Successfully evacuating, the Star Fox team reunite with Peppy and ROB, who survived the crash via an escape pod and reveal the other infectees have been cured, including General Pepper. Satisfied, Fox thanks his friends as they head for home.