C\'est en 1993 que se forme Melechesh dans la ville trois fois saintes de Jerusalem dans le but de créer un groupe de raw black metal avec toutefois une influence musicale méditerranéenne.
Un an plus tard, le line up se stabilise et le groupe commence à donner des concerts.
La sortie de \"As Jerusalem Burns\" en 1993 reçu un très bon accueil. Dans le même temps, Melechesh connait des démélés juridiques pour des pratiques occultes perpétrés dans les villes saintes de Bethlehem et de Jerusalem et les autorités soupçonnent le groupe. Tout fut éclairci quelques années plus tard.
En 1996 Melechesh sort un 7EP un titre intitulé The Siege Of Lachish' sous le label allemand Membrum Propaganda. Cette même année, le groupe est signé chez le label américain indépendant, Breath of Night Records, qui réédite leur premier album en collaboration avec Pulverizer Records (USA)
En 1997, Melechesh donne de nombreux concerts en Terre Sainte et un documentaire leur est consacré. Il sera diffusé de nombreuses fois vu les taux d\'écoute qu\'il fait.
En 1998 un CD promo est enregistré pour présenter leur nouveau style pionnier dans le Metal extrême. Cette même année, le groupe déménage au Pays-Bas et en France.
En 1999, le batteur texan d\'Absu, Proscriptor rejoint le groupe.
En 2000, les membres se retrouvent au Pays-Bas pour enregistrer leur second album, Djinn aux studio Harrow. Osmose leur signe un contrat pour trois albums.
C\'est en 2001 que Melechesh sort finalement Djinn chez Osmose Productions. Un Clip est filmé au Pays Bas pour promouvoir leur album, il est diffusé sur Internet et au Pays-Bas, en Belgique, en France, en Allemagne, aux USA, en Finlande, en Suède et en Bulgarie.
En décembre 2002, Melechesh enregistre leur troisième opus opus intitulé Sphynx au Los Angered Studios à Gothenburg en Suède par le bien connu Andy Larocque (Guitariste de King Diamond). La couverture de l\'album sera réalisée par Ron Woodall (Star Wars, Jurassic Park, Pearl Harbor etc.) à San Francisco pas le George Lucas' Industrial Light and Magic.
En mai 2003, la distribution mondiale de Sphynx obtient un excellent accueil par tous les media. Sphynx est même considéré par une majorité de fans mais surtout de media du Metal comme faisant partie du top 10 2003.
