The game takes place two years after Banjo and Kazooie killed Gruntilda in the last game. It then shows that she was buried under a large rock, and her assistant, Klungo, is trying to lift the rock off of her.
The game then shows Banjo, Kazooie, Mumbo Jumbo, and Bottles playing poker on a windy and stormy night. Meanwhile, the Hag 1 is tunneling out of a wall outside of Banjos house, and the house shakes. Mumbo goes outside to see what is happening. Meanwhile, Klungo, Blobella, and Mingella are resurrecting their dead sister. After destroying the rock, they resurrect Grunty, and see that she is only a walking and talking skeleton with witch clothes on. They begin to go back to the castle, when Mumbo is seen running back to the house- he witnessed it all. Grunty starts running after him, shooting spells, but missing every time. She then charges up a very deadly spell.
As Mumbo gets inside, he warns them that Grunty is going to destroy the house, and that they must get out. All of them get out- except for Bottles, who thinks this is just a trick, as Kazooie did earlier. Grunty's spell is then done, it blasts the house, with Bottles still inside. Grunty and the others speed away (Although leaving Klungo) in the Hag 1.
As the sun comes up, Banjo, Kazooie, and Mumbo watch as a burnt to the crisp Bottles comes stumbling out, and dies at their feet. They agree to get Grunty for this. Mumbo then returns to his hut.
Banjo and Kazooie then follow the tracks left by the Hag 1, leading them to Jinjo Village, the place where Jinjos live, or they used to. The Jinjos ran away, as the Hag 1 sped through (even killing the gray Jinjo family.)
The two then go to see King Jingaling, who tells them that he needs the Jinjos for a Kickball tournament. The two then agree to find his subjects. The Jinjo King then gives the two a Jiggy. As the two leave, the screen then switches to Gruntilda's castle, and it is revealed that Gruntys sisters have created a B.O.B. (Short for Big Ol' Blaster), a giant laser that can suck the life force out of things, and transmit the energy to another person (Grunty). They let Grunty use it, but only if she stops speaking in rhymes. Grunty agrees, and blasts the giant laser at King Jingalings palace. The energy is sucked out of the palace, and Jingaling, turning his palace a gray colour, and turning him into a zombie. Grunty then wishes to blast the whole island; however, she can not, as with each blast, it takes hours for the machine to start back up again. Blobella then says that Banjo and Kazooie will seek revenge. Grunty then reassures them, without Jingaling and bottles, no one will be able to help them now.
Banjo and Kazooie then go to world from world, collecting Jiggies as they progress. They finally collect 90 Jiggies, and make their way up to Cauldron Keep. After defeating Klungo for the last time, and defeating the Tower of Tragedy Quiz, they make their way to the control panel of the B.O.B., They then use it to revive King Jingaling and Bottles. They go home to party, and, much to their surprise, Klungo joins them, saying he is tired of serving Grunty. Banjo and Kazooie make there way up to the top of the castle. They then fight Grunty, who is hiding in the Hag 1. After being defeated, everybody is happy and parties, and kicks around Grunty's head. She then swears revenge, saying she'll get them, in Banjo-Threeie.