The clear and sharp recording of the new demo procured them three of the most important deals of their career: Century Media Records for Europe and Americas, V2 for Italy and King Records for Japan. In January 2003 Labyrinth began the recording for the new album which is titled simply "Labyrinth", under the production of the band. It was recorded at Noise Factory in Milan (Italy), and it was mastered at House of Audio in Germany, and this gave an incredible power to the album. In the meantime the problems with the old Italian label were smoothed out.
Roberto Tiranti took part in the musical The Ten Commandments which was a supplement to his activity as Labyrinth singer until the beginning of the year 2004. The released of "Labyrinth" fixed for June the 30th , wass postponed in Italy to July the 4th.
The following step after the release of the album was finding another good guitarist for the live dates. The guys found in Pier Gonella, old friend of Roberto and Andrea De Paoli, the perfect union of speed and technique. The first show with Pier was the IX Agglutination Metal Festival in Chiaromonte (PZ), where Labyrinth would have been the 3rd band, before Vader and Virgin Steele.
Just after summer 2003, began the preparation for the live show to support the new album. It was a tour out of the usual standard, without an estimated end: The Maze On Tour 2003/04.
The band organized, on March 2002, a tour called Italian Attack. A festival in which Domine, White Skull, Skylark, Novembre and Centurion took part. The incredible participation of the people took even higher the name Labyrinth, which saw in the near future the new chapter of its history.
The writing of the new tracks happened in the month of May of the same year and in the meantime Olaf Thorsen left the band to join Vision Divine, whereas Mat Stancioiu (Mattia Stancioiu) and Andrew McPauls (Andrea De Paoli) left Vision Divine to dedicate themselves completely to Labyrinth.
In the month of July 2002 is published the first demo of the new Labyrinth album. The bandmates decided to use their Italian names: Andrea Cantarelli(Anders Rain) - guitar, Roberto Tiranti (Rob Tyrant) - vocals, Andrea De Paoli (Andrew McPauls) - keyboards, Cristiano Bertocchi (Chris Breeze) - bass, and Mattia Stancioiu (Mat Stancioiu) - drum.
With such a great response the band organized an Italian tour first, in February 2001 with support band Sigma (ex Love Machine), and then a long European tour, supporting Helloween first and then with Nocturnal Rites supporting Iron Savior.
After these festivals the band entered the recording studio again to release the new full-length LP "Sons Of Thunder". As showcase for the new album, the band played at the most important European festivals, like WACKEN 2000 and Rock Machina 2000 (Spain), having indescribable success.
At the end of August 2000 "Sons Of Thunder" flew at number 52 of the Japanese chart and at the 26 of the Italian chart. Such good results were rewarded with the request of touring in South America with Vision Divine and promotion was very good.
In the meanwhile Rob Tyrant (Roberto Tiranti) got back to the band, replacing Morby and singing with Labyrinth in the most important European Heavy Metal festivals (Gods of Metal, Dynamo and more).
Shortly after the release of the new record the singer Rob Tyrant (Roberto Tiranti) left the band, being replaced by the lead singer Morby from Domine who led Labyrinth throughout the whole European tour as supporting act with Pegazus of the most popoular bands Hammerfall and Primal Fear. After some months followed an Italian Tour with Heimdall.
After a short break the band entered the recording studio to release the new Mini CD "Timeless Crime", containing new hits and old tracks from the first demotape "Midnight Resistance" to LPs "No Limits" and "Return to Heaven Denied".
Frank Andiver - drummer and Ken Taylor - keyboards left the band and the new vocalist Rob Tyrant (Roberto Tiranti), Mat Stancioiu (Mattia Stancioiu) - drummer and Andrew McPauls (Andrea De Paoli) - keyboards joined the band. In the meantime some of the most important big metal labels showed a deep interest on the band's new demo and finally Metal Blade made the best offer and the deal was signed! It took six months to record the second album "Return To Heaven Denied" and before its release the band took part to summer 1998's metal main event: "Gods of Metal", together with some of Heavy Metal biggest acts such as Blak Sabbath, Pantera, Helloween, Blind Guardian, Stratovarius. "Return To Heaven Denied" was a success among fans and metal magazines and it gave a strong impulse not only to the career of the band, but also to the whole Italian metal scene, that recognized Labyrinth as the new sensation of the moment.
"No Limits" was released and the interest on the band got higher and higher among metal kids and independent labels. The popularity of the band increased not only in the mother land and in Europe, but also overseas (Japan, Korea, Brasil), where some labels (Teichiku for Japan) offered to deal the record out. The band stayed in the metal magazine "Burrn!" top ten charts for almost six months.
Joe Terry (Fabio Tordiglione), the lead singer left the band, later frontman with Rhapsody.
The band managed to release the first demo "Midnight Resistance" that is now a cult-item among the fans. The demo got enthusiastic reviews on major metal magazines in Italy and Germany and that gave the band the chance to sign with Underground Symphony, a new-born indie.
Andrea Bartoletti - bass left the band and Chris Breeze (Cristiano Bertocchi) joined the band.
It was the year of "Piece of Time", their first EP, that marked the direction the band was taking: pure melodic speed metal with a keyboards-background that fascinates the Italian and German underground metal scene. It was the first step towards the release of a full-lenght LP.
The original line-up got together in 1991 Frank Andiver - drum, Andrea Bartoletti - bass guitar, Andrea Cantarelli - lead guitar, Carlo Andrea Magnani - lead guitar, Fabio Tordiglione - vocals, as it happens to all successful bands.