В 1995 году музыканты записывают демо-кассету "As Jerusalem Burns... Al' Intisar". Помимо Ashmedi, Moloch и Lord Curse в записи приняли участие Thamuz (бас-гитара) и Cimeries (клавишные). Демо привлекло внимание блэк-метал андеграунда и за короткий период собрало положительные отзывы. Вместе с тем у MELECHESH возникли проблемы. Местная пресса также отреагировала на демо-запись, и иерусалимская газета “Call H'Ayr” написала большую статью о группе, поместив ее на первую полосу. Однако эта публикация пользы музыкантам не принесла, более того, повлекла ощутимые сложности. В данной статье MELECHESH обвинили в оккультной деятельности и отправлении сатанинского культа. В результате на группу ополчились и стали оказывать давление местные власти.

Вопреки гонениям группу все же заметили, и в 1996 году немецкий лейбл Devilish Music Propaganda предложил парням записать 7" EP. Мини-альбом получил название "The Siege of Lachish" и был выпущен тиражом 666 копий. Примечательно, что заглавный трек в целом был написан еще перед записью первого демо, но не был использован. Завершенную форму песня обрела только на данном ЕР, наиболее полно продемонстрировав фирменный Mesopotamian Black metal, в основе которого специфические ближневосточные гитарные риффы и ритмы, исполненные в блэк-метал ключе. Сама песня была вдохновлена написанным ассирийским царем Синаххерибом древним текстом, в котором он засвидетельствовал вторжение своей армии в город Лахиш. Второй трек "Malek Al Nar" ("Король огня" по-арабски) – это скоростной и традиционный блэк-метал.

"The Siege of Lachish" укрепил авторитет MELECHESH в андеграунде, позволив подписать контракт с американским лейблом Breath of Night Records, который предложил группе переписать демо 1995 года для выпуска на CD в качестве полноформатного альбома. В том же году MELECHESH отправляются в профессиональную студию для записи. К тому времени Thamuz и Cimeries уже выбыли из состава, и партии баса записал Ashmedi.

Дебютный полноформат, названный как и демо "As Jerusalem Burns... Al' Intisar", вышел в 1996 году сразу на двух андеграундных лейблах: Breath of Night Records и Pulverizer Records. Альбом был очень хорошо принят слушателем. Группа начала играть концерты, в связи с чем состав был дополнен новым участником – бас-гитаристом Al' Hazred.

В 1998 году группа подготовила 5 новых песен (включая новую версию "The Siege of Lachish") и выпустила их в виде промо CD "Mesopotamian Metal", который был разослан лейблам с целью подписания контракта на выпуск следующего альбома. Вскоре после записи промо Al' Hazred с Ashmedi переезжают жить в Голландию, поскольку на группу продолжает оказываться давление со стороны местных религиозных общин и властей, в том числе и полиции. В 1999 году примеру своих коллег последовал и Moloch, переехав жить во Францию. Это позволило продолжить историю MELECHESH в более спокойной обстановке.

Таким образом, все участники команды, за исключением барабанщика, покинули Святую землю. В силу личных причин Lord Curse решил остаться в Иерусалиме, а позже переехал в США, где получил художественное образование и стал работать в кинокомпании Джорджа Лукаса.

Новым барабанщиком MELECHESH стал Proscriptor из культовой американской формации ABSU, в своем творчестве также затрагивающей сюжеты шумерской мифологии. В этом составе в 2000 году группа приступает к записи следующего альбома, получившего название “Djinn”. Альбом вышел в 2001 году на легендарном французском лейбле Osmose, с которым группа подписала контракт на выпуск трех альбомов. В поддержку нового альбома было снято видео “Genies, Sorcerers and Mesopotamian Nights”.

После затишья, связанного с проблемами на родине и последующим переездом в Европу, у группы наступил активный творческий период, и уже в 2003 году выходит третий альбом “Sphynx”. По сравнению с предшественником новый альбом звучал агрессивнее и сложнее. Гостевое участие в записи принял Энди ЛяРок (King Diamond), отметившись на треке "Purifier of the Stars". Лимитированная версия альбома включала в себя кавер на классику Celtic Frost "Babylon Fell". По мнению ряда музыкальных изданий альбом вошел в десятку лучших метал-релизов за 2003 год.

В 2004 году Profound Lore Records выпускает на виниле ограниченным тиражом в 500 копий EP “The Ziggurat Scrolls”, на который вошли ремиксы и демо-версии ранее уже известных песен. В этот же период Proscriptor решает покинуть группу. Расставание прошло по обоюдному согласию, и музыканты сохранили хорошие отношения. Новым барабанщиком MELECHESH становится Xul.

В 2006 году был записан четвертый альбом, получивший название “Emissaries”. Новый альбом стал очень успешным, собрав массу положительных отзывов, и смог продвинуть MELECHESH на новый уровень. Ashmedi решил начать съемку документального фильма о его творческом пути с MELECHESH. К сожалению, весь первоначальный материал, снятый в Иерусалиме, был утрачен режиссером, вследствие чего он покидает проект. Однако дело было продолжено, и ему на смену был приглашен другой режиссер. Вместе с тем Ashmedi начинает писать серию биографических статьей, которые неожиданно стали достаточно востребованы. Эти статьи публиковались в различных интернет и печатных изданиях, таких как журналы Decibel и Legacy, были переведены на несколько языков.

В 2010 году выходит следующий альбом MELECHESH “The Epigenesis”. Альбом был записан в Турции, в Стамбуле, при участии местных сессионных музыкантов. В связи с тем, что Al' Hazred решил покинуть группу, новым басистом становится Rahm. При этом часть партий бас-гитары Ashmedi исполнил на альбоме сам. Снят новый клип на “Grand Gathas Of Baal Sin”. Продвигая альбом, группа активно гастролирует по всему миру и принимает участие во множестве фестивалей.

MELECHESH подписывают долгосрочный контракт с Nuclear Blast, и в 2012 году записывают цифровой ЕР “Mystics of the Pillar II”. Однако в плане целостности для группы наступает весьма неблагоприятный период. 13 августа 2013 года на официальной Facebook странице MELECHESH было объявлено, что Moloch уходит из группы, чтобы продолжить заниматься своей научной карьерой. Место второго гитариста занял Sirius, но был уволен после единственного концерта. Также выяснилось, что был уволен и барабанщик Xul, место которого долгое время оставалось вакантным. В этот же период из группы уходит и бас-гитарист Rahm. Группе пришлось прибегнуть к услугам многочисленных сессионных музыкантов, в числе которых был и Ральф Сантолла. (Death, Iced Earth, Obituary, Deicide etc.)

Вся эта кадровая чехарда не слишком способствовала творческой атмосфере, и следующий альбом MELECHESH “Enki” вышел только в 2015 году. К началу работы над альбомом Moloch все же решил вернуться и принять участие в его сочинении и записи. Ударные на “Enki” были записаны оригинальным барабанщиком MELECHESH Lord Curse. К сожалению, как и в случае с Moloch, его участие также ограничивалось только работой в студии. Партии бас-гитары былы записаны Scorpios, который с 2013 года являлся концертным басистом MELECHESH. В качестве гостей в записи “Enki” приняли участие Sakis Tolis (Rotting Christ), Max Cavalera (ex-Sepultura, Soulfly) и Rob Caggiano (Anthrax, Volbeat)