The Labyrinth of Time is the fifth secret dungeon, and a new addition to the game for the AE version.
Unlocking
The Labyrinth is only available once the Four Fiends (Lich, Marilith, Kraken, and Tiamat) are defeated. (See the main walkthrough for details.)
Once the Four are defeated, head back to Cornelia town and talk to the shadowy figure standing around the fountain. Once he runs off, follow him to the Chaos Shrine. You will see he use a secret door at the back of the Shrine; once he's gone go to the same spot and press 
to open the door.
As you walked through the Shadowy, character still went to the back and opened the door. When you first get to talk to the character, you must pay attention to what he says, he explains the trials to you.
"Herein lies the Labyrinth of time--the dominion of he who roams myriad eons, the Master of Time." "Transcending time and space, the master now occupies this shrine." "Ye who seek to journey forth would do well to heed my words." Pick yes to continue with the explanation. "Devices and puzzles designed to test your mettle abound within the halls of the labyrinth." "The miasma drains the power of those out of time, and the monsters soon swarm the weak."Sacrifice an ability to the Light of time beforehand to buy time to keep the miasma at bay." Meaning you must sac. one of the abilities attack, magic, item etc. stops the game from killing you through the trails. Right now I'm level 46 to 48, so lets go.. "Only by solving the mysteries of each floor can you progress through the labyrinth. Near each device and puzzle there is a tablet. Consult the tablet to activate the floor. those who overcome challenges with time left break the blue seal,revealing the path proven." "Those who proceed after time has run out break the red seal, to a place befitting their powers.....it goes without saying there is no turning back. Bear this in mind as you go forth." Ending in your choice to go and try the trails or go and work on the ending of the game, remember at anytime you can cast exit, warp, etc. to go back and try the trials when you think you're ready. The weapons are awesome.
Sacrifices
Challenges
Chronodia
Chronodia is the final boss in the Labyrinth of Time after having moved up multiple levels. It turns out that the hooded figure is Chronodia and he says he lures powerful warriors. He is one tough boss to beat. He has 42,000 hit points and every 3-4 moves he casts the spell Seal which disables one of your abilities: Attack, Magic, Defense or Items. So bring a load of potions and ethers. It is much easier to beat him if you have a white mage and a black mage. The black mage's spell Flare causes 500 damage and Haste and Temper help to improve your attacks. You have to coordinate using Spells to heal and Items to heal to beat this last boss. It can take an hour or so. After you beat him, he says that he thought he was unbeatable and you get 1 experience and the status of a Fake God. He also drops the Barbarian sword that has an Attack of 157 - even more than the Ultima weapon that you get after going through the 40 levels of Whisperwind Cove.