The Lost City of the Kookamunga is an ancient mystic city, hidden by its chameleon residents from the rest of the Kookamunga.

Legends tell that the roads of the Lost City are paved in gold, and that there is beautiful architecture and an eternally moderate temperature. In the episode "Paradise Found", Iggy and Jiggers set off to find the Lost City, following directional clues from The Great Bamzeani that it lies "South of the Norse Pole, north of the south seas, west of the sun, and east of Brain Freeze". When they get there, they find that the "gold" making up the roads is actually golden rod, but that everything else about the legend is true. They find out that the city is in fact currently inhabited, and the chameleons are delighted that they are respectful of and interested in their culture. Phil, a chameleon of authority (although his exact position in the city is unclear) shows Iggy and Jiggers how self-reliant the community is - they make and process their own food, and they have their own unique style of music and abstract art.

When Catfish Stu, Robear and Robert try to take over the city to use it as a tourist attraction, Iggy and Jiggers help the chameleons to move the city to a new location. Phil tells them that this has happened 26 times in the Lost City's history; every time an outsider came into the city and tried to have their own way with it, the chameleons changed their location, and became "lost" once more.

It is revealed in subsequent episodes that the Lost City does have an impact on the outside world, as characters have been seen eating a breakfast cereal produced in the city.