The player takes the role of Raphael, a young Parisian boy, who has an alter-ego named Phantom R. He is wanted by the police, particular Inspector Vergier, due to Raphael's hobby of breaking into buildings and stealing valuable pieces of artwork, only to return them soon after. It is eventually revealed that instead of stealing them and returning them Raphael is stealing art that he knows to be forged and replacing them with the originals. The forgeries were created and put in place by Raphael's father, Isaac, who disappeared under mysterious circumstances when Raphael was young. Raphael also has to contend with a man claiming to be the original Napoleon Bonaparte, back from the dead, who attempts to thwart his interference with his army of Chevalarie Knights. Raphael is aided along the way by his faithful dog Fondue and love interest Marie, while also crossing paths with Vergier's daughter Charlie.
Gameplay in Rhythm Thief features a number of different modes. The most notable sections are the rhythm sections where the player must complete a number of actions in a certain rhythm, similar to games like Rhythm Heaven and Space Channel 5. These usually involve button presses, screen swipes with the stylus or tilting the 3DS to make use of the gyroscopic functionality. The game also has a puzzle element where players must complete puzzles to, for example, open locks.
Outside of these moments the game has a map world on the top screen of the 3DS, similar to a Mario game, and moving from point to point takes Raphael to different parts of Paris. Within these different parts the player will find many different people who can be tapped with the stylus and conversed with. The player can also tap areas of the environment, collecting coins, Phantom Notes or sounds, which can be accessed later on to solve puzzles. Coins can also be collected from completing rhythm games, and certain "boosts" can be bought before starting a game.