The demo got enthusiastic reviews in major metal magazines in Italy and Germany and that gave them the chance to sign with Underground Symphony, a new indie record label.

"Piece of Time", their first EP, marked the direction the band was taking: pure melodic speed metal with a keyboards-background.

The popularity of the band increased not only in the Italy and in Europe, but also overseas where some labels (Teichiku Records in Japan) offered to distribute the album.

In 1997, Frank Andiver (Franco Rubulotta) and Ken Taylor (Luca Contini) left the band (however they took part in the composing of "Return to Heaven Denied"); and Rob Tyrant (Roberto Tiranti), Mat Stancioiu (Mattia Stancioiu) and Andrew McPauls (Andrea De Paoli) were brought in as their replacements.

After a short break the band entered the recording studio to release the new Mini CD Timeless Crime, containing new and old tracks from the first demotape Midnight Resistance to LPs No Limits and Return to Heaven Denied.

As a showcase for the new album, the band played at important European festivals, like WACKEN 2000 and Rock Machina 2000 in Spain.

The first show with Pier was the IX Agglutination Metal Festival in Chiaromonte (PZ), where Labyrinth would have been the third band, before Vader and Virgin Steele.

The new work was a prosecution of the way begun with Labyrinth, with songs of deep atmosphere and tracks like "Just Soldier", but with a deeper introspection.

Taking part with good and dense ideas to the writing of the new tracks, Pier Gonella with the beginning of 2004 joined the band as sixth official member.

Also in December, Rob Tyrant (Roberto Trianti) recorded guest vocals on the rock opera "Genius 'Episode II'" along with people such as Eric Martin (formerly of Mr. Big), Russell Allen (from Symphony X), Jeff Martin (of Racer X), Mark Boals (formerly of Yngwie Malmsteen), Daniel Gildenlöw (of Pain of Salvation), Liv Kristine (formerly of Theatre of Tragedy), and Edu Falaschi (of Angra).

[3] Labyrinth put the band to work one more time, with big support of Century Media, in Japan good sales with King Records and then in the month of May a tour in Asia called "Banzai Tour" in Tokyo and Osaka, Japan, Taipei, Taichung, Taiwan, and Beijing, China and also Hong Kong.

After some shows in Italy, Labyrinth played in Slovakia at More Than Festival 2004 with bands like Lost Horizons, Destruction, and Freedom Call.

The Italian version of the album contained the exclusive bonus DVD with a Tokyo show (Banzai Tour 2004), "best of" London Cadmen Underworld (from 13 November 2004), the "L.Y.A.F.H."

[13] Later, on 14 August 2005, Labyrinth took part in the Metalway Festival in Gernika-Bilbao with bands like Manowar, Saxon, Accept, Motörhead, W.A.S.P.

They played only two shows with this new line up, one at Mesiano in Trento and another at the Evolution Festival,[16][17] then spent the rest of the year writing and recording 6 Days to Nowhere.

Following the album's release the band announced a tour of Europe (only one date in Sweden and the rest in Italy) and Japan, between 27 October 2007 and 2 March 2008.

[23] On 22 January 2008, it was announced that Andrea De Paoli would be making a guest appearance on the debut album of Expedition Delta, which is being released by ProgRock Records.

[26] In October 2009 was also announced the new bassist Sergio Pagnacco (with courtesy of Vanexa historical italian metal band)).

It was also announced the band's line-up reunion of founding members Olaf Thorsen and Andrea Cantarelli on guitars with Roberto Tiranti on lead vocals, along with John Macaluso (former Ark, Yngwie Malmsteen, James LaBrie, Riot, Starbreaker, and TNT) on drums, Oleg Smirnoff (former Vision Divine, Eldritch, Death SS) on keyboards and Nik Mazzucconi on bass.