Cole Gannon, a rookie in the ACME detective agency finds a set of GPS coordinates on the agency's computer server, which leads him to a museum in New York. The GPS coordinates involve a case dealing with the infamous thief Carmen Sandiego, who Cole wants to capture despite being still just in training. It seems Carmen wants to put back together a set of stolen tribal drums that will unleash an unspeakable power.

There are two other ACME operatives, Jules and Shadow, who are working on the case in Siberia at the moment so they can only help Cole with advice through email messages.

The game consists of exploring nine different locales all over the world from New York to Thailand. Each locale is broken down into several areas. Each area has different items to collect. The main items to collect are compasses. These will help in locating Carmen Sandiego's whereabouts. Another item Cole can collect are puzzle pieces. Collecting these will unlock a jigsaw puzzle for Cole to solve.

Also for Cole to make his way through areas, he has to defeat some enemy combatants who possess key codes. A few key codes are needed to unlock forcefields, which block the pathways to get further into the area. To defeat enemies, Cole is equipped with a staff he can use to whack enemies with. He also comes equipped with a dart gun, which he can use to hit switches he can't reach otherwise. Cole must also move stealthily through each area to avoid security measures and to get a drop on unsuspecting enemy units. Cole has other moves he can perform such as pole vaulting with his staff, rolling from a crouch position, pressing his body close to a wall, double jumping, tightrope walking, and hanging from ledges, pipes, and even ziplines.

During the game, players can access a menu with various tabs. The atlas tab gives educational factoids about the area Cole is in. The map tab gives detailed information about the area that Cole is currently exploring. The GPS tab gives information about where Carmen Sandiego will be heading next. The transport tab let's the player go back to the areas they previously explored in their current location. The communication tab lets the player receive messages from Jules and Shadow. .