Khallice started in Brasília, Distrito Federal in 1994 as a cover band, but very soon the musicians began to create their own music. The band released two demos. The first demo of the band was done in their native Portuguese. Then they recorded the song Madman Lullaby, an English version of Balada do Louco for a Tribute CD to former Mutantes member, Arnaldo Baptista. The second demo Prophecy "was received very well by the local fans, fanzines and professional magazines from all over Brazil" In June 1999 Alírio Netto, who played the part of Jesus in the Brazilian and Mexican casts of Jesus Christ Superstar joined the band as a lead vocalist. He replaced Mario Linhares who had left the band. But due to his occupation in the rock opera he could really start his work with Khallice only at the end of 2001. Finally Khallice established stable line-up and finished writing the stuff for their first album, The Journey. The band's line-up at that time consisted of Marcelo Barbosa, Alírio Netto, Michel Marciano, César Zolhof, Bruno Wambier. The Journey was recorded in November 2001 – August 2002 in Zen Studio, Brasília and included new tunes and rebuilt versions of songs written since the beginning of the band. All the songs were created by Marcelo Barbosa and Bruno Wambier. There were some progressive metal songs like Spiritual Jewel with some links and allusions to Dream Theater and classical progressive bands of the 1970s like Yes and metal hit songs like Vampire, Wrong Words, Thunderstorm and the title trackThe Journey. According to Thiago Sarkis, Whiplash.net observer, "The Journey play the same part in Brazil like Images and Words of Dream Theater is for prog metal worldwide". According to the review in Poppycorn.com Webzine: "The album includes 9 compositions with much virtuosity, a lot of guitar and keyboards solos and everything that the prog metal style offers". To the national release of The Journey Khallice played a concert with one of the most important rock bands in Brazil, Dr. Sin. With The Journey set-list Khallice played at big musical festivals like Porão do Rock and Brasília Music Festival, sharing the stage with artists such as Alanis Morissette and Simply Red. In mid-2005 the band is chosen by public vote to participate in the BMU Festival conducted at Directv Music Hall in Sao Paulo. Part of this gig was recording a video, the line up is Alírio Netto, Marcelo Barbosa,Michel Marciano, Renato Gomes and Maurício Barbosa. The first press of The Journey as a self-release was sold out in less than six months. In the beginning of 2003 it was re-released by Hellion Records and in 2007 an important progressive rock label from North AmericaMagna Carta managed a worldwide release of The Journey. Marcelo Barbosa for PerfectProg Webzine : "It happened in the beginning of this year. I went to the USA to play at NAMM and I met Greg Howe for the second time in my life. He gave some classes in 2005 and now I would like to take this opportunity again. I really like his playing, he's one of my favorites players in the world. So, I showed to him two songs of our new CD that were done at this time. He really enjoyed it and helped me with some contacts. Magna Carta was our best option". After some line-up changes, in the summer 2007 Khallice started recording of the second full-length album with the following line-up: Alírio Netto, Marcelo Barbosa, Michel Marciano, Pedro Assumpção and Renato Gomes. At the end of January 2008 the band became one of the winners of a contest announced by Dream Theater to support one of their shows during Brazilian part of the tour supporting Systematic Chaos album. On 7 March 2008 Khallice played a gig in Citibank Hall in Rio de Janeiro with Dream Theater. It was another opportunity to gather new experience and to conquer some new audience. Specially for this show Khallice prepared Inside Your Head with 5 new songs from the upcoming second album. The EP included 3 typical prog metal tracks "Inside Your Head", "In The Fire" and "Share A Little Something" and two metal ballads "Letting Go" and "Reasons". The cover artwork was created by Gustavo Sazes. The first 1.000 fans who assisted the show got copies of the new EP Inside Your Head. From the Metal Madman Webzine review : "The production is now crisp, clear, heavy, and with a solid bottom end to it. Vocals are blended perfectly in the mix, and sound incredible. The harmonies alone make this EP worth checking out! What I like about Khallice is even though they are a progressive metal band its not overly done, and the songs flow very well with great catchy melodies, and rhythms." At this point in the middle of 2007 the activities of Khallice were stopped for a while. The release of the second album was postponed due to Marcelo Barbosa's membership in Almah and the recording Fragile Equality studio album with the guitarist of Khallice.
