The story of The Labyrinth of Time is loosely based on Greek mythology. The game begins during player's commute home from work. While aboard the subway, the player and their train car are suddenly sucked into an alternate dimension. An illusion in the form of the mythological character Daedalus explains that King Minos has forced him to oversee the construction of a labyrinth that spans the space-time continuum. Upon its construction, King Minos will invade and conquer all times and places with his supernatural powers. Daedalus pleads for the player to find a way to destroy the labyrinth before Minos can complete his conquest.
In-game terminals and journal entries reveal the extent of Minos's power. As explained by the lone archivist on a lunar library, a figure identifying himself as the king appeared simultaneously to all world governments in all time periods, seizing control of their militaries and erasing all written history. Minos's new abilities seem to extend beyond time travel; the scene of the king's tomb strongly implies that he rose from the grave.
The labyrinth that the player explores spans many time periods and locations. Despite their incongruity, each area is thematically connected by the story of Martin Garret, a professor intrigued with discovering the tomb of the unnamed Sorcerer-King at a far-off ziggurat near Uxmal. Desperado Mad Dog Maddigan, the one man who knew the location of the Sorcerer-King's treasure chamber, was buried in the Western town of Revolver Springs, California, along with a map to the ziggurat's chamber. Revolver Springs, however, was destroyed in a fire on May 1, 1882, leaving the location of his grave a mystery. Garret was about to begin his second expedition to the ziggurat, but suffered from anxiety after losing his lucky shirt in a previous dig.
When the player finds the ziggurat, they can retrieve the shirt. They are also able to go back in time to Revolver Springs and pick up a newspaper explaining that the local graves were relocated to make way for a railroad extension project. The player leaves both for Garret to receive, changing history. With the encouragement and new information, Garret locates Mad Dog Maddigan and completes his expedition. Among the treasures brought back from the Sorcerer-King's tomb, Garret discovers a talisman that was reputedly used to destroy buildings.
The player must operate three levers in the ziggurat to reach the center of the labyrinth and take, among other items, the talisman to destroy its keystone. After dispelling an illusory Minotaur guarding the Maze Center, the player breaks the maze's keystone. This causes the labyrinth to unfurl at the seams. Daedalus appears in person to offer thanks for his freedom, then leaves to ensure King Minos can do no more harm. He leaves the player floating in an area that does not exist in time or space.