The player assumes the role of Anya Romanov, an acrobatic, high-tech professional thief living in the futuristic dark metropolis Forge City. Her initial mission is to infiltrate a high-security museum and steal items therein. She is assisted by the computer expert Louie Palmer, who communicates with her through an earpiece. Later on however Anya is framed for murder she didn't commit and finds out about a sinister conspiracy involving a ruthless corrupt politician Richard Killian and her own deadly female ninja rival known only as Breeze.
Anya has several hi-tech gadgets to assist her, including night vision goggles and a multi-use dart gun. Notably, Anya has no lethal arms at her disposal: because of her personal moral code the player cannot kill any of the guards and other enemies she encounters, and can only knock them unconscious for a brief moment. According to the IGN review, "it's clear that the developers have played Splinter Cell and Metal Gear Solid games, but they haven't learned how to make it all that interesting." The GameSpot review mentioned the game's "Prince of Persia-inspired feats", however "the only difficult part about Stolen is finding the patience to actually remain hidden when it's easier to just charge through the levels."
While Stolen received little press coverage, that which it did receive was mostly poor (GameRankings average scores of 52.89% for the PC version, 56.43% for the PS2 version, and 54.42% for the Xbox version). IGN reviewer called the game's action "incredibly uninspired", concluding that "it's a game like this that truly makes one appreciate all the other stealth games on the market."