Sly 2: Band of Thieves takes place two years after the events of Sly Cooper and the Thievius Raccoonus. The game follows Sly Cooper, Bentley, and Murray as they travel the world to defeat the Klaww Gang and obtain the Clockwerk parts.
The Cooper Gang breaks into the Cairo Museum of Natural History in order to steal the Clockwerk parts. However, they are caught by Inspector Carmelita Fox and Constable Neyla, who mention that the parts have already been stolen. Neyla purposely hints that the parts might have been stolen by a group of criminals known as the Klaww Gang. After escaping the museum, the Cooper Gang begins tracking down the Klaww Gang.
The trio first travel to Paris and steal the Clockwerk Tail Feathers back from Dimitri Lousteau, a club owner and "underworld celebrity," who was using the feathers as a printing press for forged money due their unique alloy being unaffected to wear. While there, Sly is confronted by Neyla, who claims that she wants to help the Gang collect and destroy the Clockwerk parts. After putting the forger behind bars, the gang heads off to India, where they steal back the Clockwerk Wings from Rajan, a tiger who controls the Klaww Gang's illegal spice operations and uses the wings to earn prestige. After pursuing Rajan into the jungle, the trio manage to steal back the Clockwerk Heart. Unfortunately, the gang is double-crossed by Neyla, who gets them, along with a framed Carmelita, arrested by The Contessa, a high-ranking prison warden whose mastery of hypnosis to "re-educate" criminals has earned her a reputation within Interpol.
Being the only one to not be captured, Bentley travels to Prague to free Sly and Murray from the Contessa's prison. In the process, he learns that she too is a Klaww Gang member, using the illegal spice as part of her hypnosis techniques so that the thieves in her care will confess where they've hidden all of their wealth. Though the Contessa initially escapes, the gang tracks her down and steals the Clockwerk Eyes from her, freeing Carmelita in the process. The prison warden is brought to trial for the crimes she committed, and Carmelita reluctantly takes Sly's help in an escape (still being a framed cop).
The gang then tracks down Klaww Gang member Jean Bison to steal the Clockwerk lungs, stomach, and talons. However, Bison captures the three of them at his lumber camp and sells all of their Clockwerk parts to the final Klaww Gang member, Arpeggio. The trio defeats Bison and sneaks on-board Arpeggio's airship as part of a Trojan Horse-type plan. In doing so, they are forced leave the team van behind, much to Murray's dismay.
The trio's journey culminates in a confrontation with Arpeggio. They learn that him and Neyla have been working together all along and have managed to reconstruct Clockwerk's body. Arpeggio reveals that he intends hypnotize the citizens of Paris (that have consumed spice from Dimitri's nightclub) into a state of rage and hatred in order to obtain immortality after he has merged with Clockwerk's body. However, Neyla double-crosses him and bonds with Clockwerk herself. Dubbing herself "Clock-La," she crushes Arpeggio in her beak and flies away.
Knowing they need to act fast, the gang disables the blimp's engines to stop Clock-La from drawing energy. After some help from Carmelita, the mechanical hybrid is beaten and crashes down in Paris. Bentley manages to grab Clock-La's Hate Chip, but his legs are crushed by her beak in the process. Murray manages to free him before Clock-La explodes. Carmelita, who is angry at not having had a whack at Clock-La herself, smashes the Hate Chip, thereby killing Neyla and ending Clockwerk's reign of terror on the Cooper Clan.
Carmelita suddenly places all three of the thieves under arrest, but Sly decides to give himself up peacefully in exchange for letting Murray and Bentley go. Carmelita, who is reinstated as an Interpol agent and given a promotion by her boss, takes Sly on-board a helicopter. Although initially silent, the two begin conversing about past adventures and interests, prompting Sly to relate it to a first date. However, as Carmelita is about to share some champagne she'd been saving for Sly's arrest, she realizes that the short journey has taken over two hours. Whilst she checks the cockpit, Sly realizes that Bentley and Murray left him with a little parting gift by rigging the chopper to fly in circles. As Sly makes his escape by paragliding out of the chopper, Carmelita remarks that she'll see him again soon.