Two months after Gruntilda was buried under a rock in Spiral Mountain in the original Banjo-Kazooie. As no matter how much he tried, Klungo couldn't push the rock and unblock his master, he built her a mechanical body to host her spirit and get revenge on Banjo and Kazooie. Mumbo Jumbo, who watched everything behind a bush, rushes to warn Banjo about the witch's return but she still manages to kidnap the bird, forcing the shaman to send the bear back in time so he can rescue his friend and stop Gruntilda once again.
Banjo then arrives at Spiral Mountain from the past and meets Bottles' ancestor, Bozzeye, who offers to teach the bear and, eventually, Kazooie too the moves they have forgotten due to the time travel's side effects in exchange of Musical Notes. He eventually rescues his friend in Breegull Beach, and the two continue to gather Jiggies for Master Jiggywiggy in order to enter Gruntilda's Lair and defeat her spirit.
After Gruntilda is defeated, she is sent back to the present time and orders Klungo to send a message to her sisters, Mingella and Blobbelda, so they can break the rock as the minion would never be able to. If the game is not 100% completed, Mumbo from the past uses a spell to send Banjo and Kazooie back to the present but fails and they reach their house with various copies of each other. If the game is 100% completed, however, they meet three purple Jinjos who are commemorating how Gruntilda was defeated and they'll finally be able to reclaim their homeland, Spiral Mountain. A scene of Mumbo and Honey B doing the "bee dance" inside Mumbo's Skull is then shown, with the shaman saying he might even be able to show her his "special transformation".
The Jinjo Oracle appears in every world. As the voice the Jinjo community, the she request Banjo and Kazooie to find the five missing Jinjos in a world. After doing so, the Jinjo Oracle rewards them with a Jiggy. For each Jinjo they recover, Banjo and Kazooie can optionally visit the Jinjo Oracle for some gameplay advice.
Mr. Ripovski is a mouse and a businessperson. He appears in nearly every world, each under a different guise. In Breegull Beach, he is a scavenger who asks Banjo and Kazooie to retrieve some seashells for him. In Spiller's Harbor, he is a sideshow host. In Freezing Furnace, he has an antagonistic role, where Banjo must stop him and two other mice from stealing Snowies during the Snowy Sleds minigame.
One Dolphin appears in Breegull Beach, and asks Banjo to help remove a "shiny thing" (Jiggy) blocking the entrance to his house. Another appears in Spiral Mountain, and it asks to be fed ten Blue Eggs.
Aside from Mrs. Squitter, there are only two Squits, both of whom are her children. Banjo can return the Squits to Mrs. Squitter by giving ice cream to one and retrieving a spaceship toy for the other.
Mecha-Grunty is a mechanical suit that Klungo created to host Grunty's spirit, due to her body being trapped beneath a rock. She is the only other main boss aside from Klungo. A giant version of her is fought in Spiller's Harbor.
As an octopus, Banjo can swim in harmful waters in the last two worlds, Spiller's Harbor and Freezing Furance, and dive underwater without losing air supply. In this form, Banjo can attack by squirting water jets.
As a tank, Banjo can move across acid without taking damage. He can shoot missiles which blast open doors that only the tank transformation. Banjo cannot jump in this form, so he must avoid falling off an edge.
The first level is a typical farm area, featuring barns, green grass, farm animals, and bales of hay. The level features numerous Gruntweeds and Gruntlings. Cliff Farm is where Banjo first battles against Klungo.
The game's music was composed by Jamie Hughes instead of Grant Kirkhope, composer of the console titles. Sound effects are sticking true to the classic sounds of Banjo-Kazooie and Tooie. However since the Game Boy Advence games aren’t able to store as many sounds in their memory as the N64 games, characters’ voices are comprised of less sounds, and thus some voices sound repetitive.
Many continuity-based plot holes are caused by this game being released significantly later than the other two and taking place both between them and before either of them. Most of these are related to character design and knowledge of one another, in that due to this game, Banjo and Kazooie should know of Klungo, Jiggywiggy, and Honey B. by the time of Banjo-Tooie, but act as though they had never met. Furthermore, Mumbo Jumbo looks like he does in Banjo-Tooie in the past, despite how in Banjo-Kazooie, only his face was a skull instead of his entire head.
Microsoft, who acquired Rare one year before this game's release, allowed THQ to publish this title and other Game Boy Advance games Rare devloped on their behalf due to most of said games already being in development before the buyout. Microsoft had no equivalent in the handheld market and did not want the development time and resources they acquired to go to waste.