In Spain 1519, two con artists, Tulio (Kevin Kline) and Miguel (Kenneth Branagh), win a map to the legendary City of Gold, El Dorado, in a rigged gambling match (though ironically they end up winning the map fairly). After being accused of cheating with loaded dice, the two evade capture while being chased by a bull and hide in barrels, which are shortly loaded onto one of the ships to be led by Hernán Cortés (Jim Cummings) to the New World. During the trip, they are caught as stowaways, but manage to break free and take a rowboat with the help of Cortés' horse, Altivo (Frank Welker). They land at an unknown shore at the edge of Mexico, and Miguel begins to recognize landmarks stated on the map. The map leads them to a totem marker outside of a waterfall where a young woman approaches them, chased by a number of guards. The guards see the image of Tulio and Miguel riding Altivo as the same on the totem, and believing them to be gods, escort them and the woman under the falls and into El Dorado, truly a city made of gold.
Tulio and Miguel are brought to the city's elders, Chief Tannabok (Edward James Olmos) and wicked high priest Tzekel-Kan (Armand Assante). While Tannabok warmly welcomes them to the city, Tzekel-Kan mainly sees them as a way to enhance his own standing. Tzekel-Kan also believes that with the arrival of the gods comes "The Year of the Jaguar", a year in which the city will be purged of all wicked people. Tulio and Miguel begin to argue on what to do. Everyone is convinced they are gods when as a volcano is beginning to erupt, Tulio yells at Miguel to stop, and the volcano suddenly stops. After celebrations offered by both Tannabok and Tzekel-Kan, the two are taken to private quarters along with the woman they met earlier, Chel (Rosie Perez), who has seen through their ploy but offers to help maintain it as long as they give her a share of the gold and take her with them when they leave. Tulio tells Tannabok the next day that they are only here for a visit, but will need a boat to leave the city with the gifts the city has showered upon them.
Tannabok says it will take them at least three days to construct a vessel to carry both them and the gifts given to them by the people of El Dorado. Chel encourages Miguel to continue to explore the city while she tries to get close to Tulio. Miguel finds the streets empty and sees and old man being punished by a guard, who tells him Tzekel-Kan had ordered the streets cleared to prepare for a sacrifice by gods orders. Miguel begins playing a guitar and begins to bond with the people. When Tzekel-Kan sees Miguel playing a ball game with children, he demands that the gods play against the city's best players. During the match, Tulio and Miguel are clearly over-matched, but Chel replaces the ball with an armadillo named Bibo, allowing the two to cheat and win the game. However, when Tzekel-Kan offers to have the defeated players put to death and tell them they must punish the wicked, Miguel sees that no one there is evil and orders him to leave the city saying the gods will speak for themselves.
As he is leaving, Tzekel-Kan sees a small cut on Miguel's forehead, and realizes that they are not gods because gods do not bleed. Tzekel-Kan conjures a giant stone jaguar to chase them through the city. Tulio and Miguel manage to outwit the stone jaguar, causing both it and Tzekel-Kan to fall into a giant whirlpool, thought to be the entrance to Xibalba, the spirit world. Tzekel-Kan comes to outside El Dorado, where Cortés and his men are searching for gold. Thinking Cortés is a true god, Tzekel-Kan quickly offers to lead them to El Dorado. With their boat completed and loaded with treasures, Tulio is ready to leave but Miguel announces that he will be staying because he finds the city peaceful. As Tulio and Chel start to leave, they spot smoke on the horizon, realizing that Cortés and his men are approaching the city with the help from Tzekel-Kan. To protect the city from the Spanish troops, Tulio determines they can use the boat to slam against rock formations under the waterfall path that will cave in and block access to the city.
The city residents pull down a large statue to create a wave to propel the boat, but Tulio cannot get the sails up to give the boat enough speed to avoid the statue. Miguel forgoes his chance to stay in the city and jumps into the boat with Altivo to finish hoisting the sails. The boat clears the statue in time, and Tulio's plan is successful; though the boat and its treasures are lost, the entrance to El Dorado is sealed for good. Tulio, Miguel, Chel and Altivo hide as Tzekel-Kan brings Cortés and his men towards the waterfall. Once Tzekal-Kan finds out that the entrance has been blocked, an angry Cortés takes this as a lie. Cortés and his men then march away with a humiliated Tzekel-Kan in their hands. Tulio and Miguel though disappointed they lost their treasure, take off in a different direction for a new adventure, unaware that Altivo still wears the golden horseshoes he was outfitted with in the city.