Formed in 2001 under the name of KYMERA, the lads changed the name to BLACK MAJESTY after their first line-up change. The two musicians could already look back on a busy musical career in various metal bands in the Melbourne area. After sorting everything out they began the songwriting for their debut album, "Sands of Time" which was released two years later. The album leaned in the prog direction but they followed the styles of Queensryche, Jag Panzer and Iron Maiden and it was this which attracted the attention of Limb Music Products, who quickly placed BLACK MAJESTY under contract. The company has remained true to the band until this day, an example of the harmonious and productive collaboration between them. "Sands Of Time" hit Europe like a hammer and the band quickly found itself amongst the top newcomers of the year. In numerous online polls the album was even voted "Album of the Year".

Encouraged by this success they played live shows and then began work on the follow-up album. 2005 saw the release of "Silent Company", on which they clearly left the progressive path, hitting the faster lanes of driving, melodic Power Metal. Drummer Pavel Konvalinka recorded his drum parts for this album in Germany at Piet Sielck's studio (Iron Savior), whilst the rest of the band recorded their tracks with Endel Rivers in Melbourne. To promote the album's release, BLACK MAJESTY played their first European shows, amongst them festivals alongside Hammerfall and Edguy. Then it was back home for a tour with Nevermore and Dragonforce.

"Tomorrowland", the Aussie's third album was released in June 2007. The style followed that of its predecessor but their special elements were intensified. Once again they had the chance to play live in Europe. Beside solo shows they were invited to play at the world's greatest and truest metal festival, the Wacken Open-Air, as well as at the Masters of Rock in the Czech Republic and the Metal Universe Festival in Slovakia. The album proved to be yet another success and allowed the band to tour with international acts back in Australia. They opened for Helloween on their tour and a little later supported Saxon in the land of Oz.

It is worth mentioning that, during all this time, BLACK MAJESTY never had a bass player of their own. In the studios, on tour and for headliner shows of their own, they always relied on bass-playing mates. And this also applies to their fourth album. The fans had to wait three long years for the follow-up to "Tomorrowland" warten. "In Your Honour" makes it absolutely clear that BLACK MAJESTY are amongst the best Power Metal bands which have ever hit Europe from the world's youngest continent.

Even during the work on their new album, the band was on the road, playing live. They supported the ex-Iron Maiden singer, Paul DiAnno and Edguy at several Australian shows and even headlined the Bla Bla Bla Festival in Jakarta, Indonesia.