樂隊在成立後的兩年里並沒有著急錄製正式的作品，而是通過不斷的排練來提高自己的水平，在此期間只是在排練期間作過幾次簡單的錄音。直到1995年，積累了足夠經驗的樂隊才錄製了自己的第一張Demo As Jerusalem Burns...Al' Intisar（名字讓我想起了MARDUK的名作Heaven Shall Burn...As We Are Gathered）。如同早期黑金屬作品一樣，這張Demo用“簡單、粗暴”的手法表達了對偽善宗教的仇恨，而來自耶路撒冷的事實也為樂隊增添了不少神秘感，這一切使得這張尚顯幼稚的作品在當時的地下黑金屬圈內得到了相當的好評。
melechesh
媒體事件
然而就在As Jerusalem Burns...Al' Intisar完成後不久，樂隊就迎來了一次致命的危機。這次危機起源於MELECHESH接受的一次採訪，採訪他們的報紙名為H'Ayr，是耶路撒冷的主要媒體之一，在採訪中，樂隊毫無機心的大談特談自己的祖先並不是猶太人，而是亞述人（Assyrian）或者說是古代的美索不達米亞人（Mesopotamian）人，樂隊的目標就是要在耶穌的誕生地（伯利恆，Bethlehem，位於耶路撒冷南方六英里的一個市鎮，相傳為耶穌的誕生之處）附近製造褻瀆云云。這篇訪談很快就發表在了H'Ayr的頭版，而樂隊在訪談中被描述成了聖城耶路撒冷里唯一的一群撒旦信徒。無論樂隊當時的真正理念是什麼，但是在接受主流媒體的採訪時發表如此大逆不道的言論確實不夠明智——巨大的輿論壓力他們可以不理會，但是當警方以樂隊的撒旦信仰違背了相關法律為名義要請他們“喝茶”之後，他們就不能不理會了。最終，他們被剝奪了以色列的公民身份。這次事件不僅對樂隊打擊很大，而且還波及到當時在以色列的其它金屬樂隊。由於MELECHESH所發表的“邪惡”言論，以色列有關部門開始對國內的金屬樂隊進行清查，幾乎所有的以色列極端金屬樂隊都受到了影響，比如前面介紹的ORPHANED LAND，在第二張專輯El Norra Alila發行後不久，就趕上了這場風波而沉寂了七年之久。
塞翁失馬，焉知非福。MELECHESH遭受的這次打擊卻大大提高了樂隊的知名度。在“採訪事件”後不久，德國廠牌Devilish Music Propaganda就邀請他們錄製一張7寸EP，這張名為The Siege of Lachish的EP唱片限量666張，但由於種種原因，真正發行的數量十分有限。同樣是在1996年，美國廠牌Breath of Night看中了樂隊早期的那張Demo作品As Jerusalem Burns...Al' Intisar，於是邀請樂隊重新進行了正式的錄製並與另一家美國廠牌Pulverizer合作發行了這張專輯。此外，依然堅持留在以色列的MELECHESH在吸收了新成員Al' Hazred作為貝司手之後還在耶路撒冷作了幾次現場演出，這也是聖城的第一次黑金屬現場演出。
為了彌補鼓手的空缺，MELECHESH邀請了著名黑金屬樂隊ABSU的鼓手Proscriptor（原名Russ R. Givens）加盟，隨後在2000年以這個完整的陣容開始在荷蘭錄製第二張專輯。2001年，這張名為Djinn的專輯正式發行，專輯的名字Djinn取自伊斯蘭傳說中的Jinn，Jinn在阿拉伯語中的意思就是魔鬼、精靈，他們具有超自然的力量，可以做許多人類無法完成的事情，而前面的D則是惡魔（Demon）的簡稱（在《一千零一夜》中，有大量關於Jinn的故事；此外，在Diablo II中，有一把非常漂亮的彎刀就叫做 Djinn Slayer）。這張專輯中大量使用了傳統的Thrash Metal手法，卻營造出了一種類似早期MAYHEM那種粗糙、原始的感覺，中東音樂元素的使用為之增添了很強的異域色彩，除此之外，他們還翻唱了SLAYER的名曲Evil Has No Boundaries（邪惡無邊界），選這首歌真是再合適不過了！
