The story begins with a young boy, named Kevin, being kidnapped from his bedroom by a group of dwarves who have just stolen a map. The map allows the holder extra-ordinary powers, by jumping from time to time through portals - holes in the fabric of space/time, depicted on the map. The dwarves stole the map from the Supreme Being, apparently a title for God. Initially they worked for him, creating the world and universe. After being demoted to the Supreme Being's repairs department, the dwarves decide to use the map, entrusted to them for use in repairing the space/time fabric, to get "stinkin' rich". However, the source of all evil (personified by actor David Warner) is also after the map to gain control of the universe from the Supreme Being.

The band of thieves roam history stealing all that they can, from medieval France through to the late nineteenth century. With the unsolicited assistance of Evil, they are translated to the Time of Legends and journey to the Fortress of Ultimate Darkness where they confront Evil. The bandits get much the worse of the encounter until the appearance of the Supreme Being, in the person of a middle-aged gentleman in a rumpled business suit who bears a very strong resemblance to Ralph Richardson.

Sean Connery (playing King Agamemnon) and former Python John Cleese (playing Robin Hood) also appear. Kenny Baker of R2-D2 fame plays one of the dwarves.

The film is the first part of a loose trilogy of fantasy films, directed by Gilliam, that includes Brazil and The Adventures of Baron Munchhausen.