Madison travels to Brazil to find her sister Abby, that was stationed on the region working for National Geographic before mysteriously disappearing. While searching for clues, she stumbles upon ancient artifacts leading to the legendary Lost City of Z.

Lost City of Z is a hidden object game with adventure elements and an archaeological theme. Like Herod's Lost Tomb by the same developers, this game is based on a National Geographic documentary, with some footage from the special being used on cutscenes between chapters. The screen shows a location with several objects scattered throughout the scenery, and the main objective is to find and click on all the items listed on a film strip at the bottom. Some portions of the scene can be clicked to open a zoom view window, often containing some of the required objects. Some of the items are stored in the inventory for later use, or inside one of four pocket pouches to be used as tools.

The first tool is a camera that has to be used to take a picture of an animal. The name of the creature is written in yellow on the list. Once selected, the player has to center the lens viewfinder on the subject and click to snap the photo. The pictures are added to the main character diary, as illustrations to entries about the fauna. They can also be accessed from the main menu and set as the desktop wallpaper. Other tools include a knife, useful to cut through thick foliage, and a flashlight to illuminate dark caves and other dimly lit locations.

Mini-games appear occasionally on separate screens, where a mechanism of some sort has to be manipulated directly. The list is usually replaced by the inventory in these sections, from where the stored objects can be dragged and dropped on logical portions of the scenery to solve puzzles. In the course of the game, the player will follow coordinates to place pins on a map and find a route, organize a series of stones on a grid, unlock a stone door with the correct sequence of keys and encounter other similar challenges.

The hint system is a GPS device that places a radar circle near one of the required objects, but takes a few minutes to recharge after use. It also shows pictures of any list entry.