Наученные горьким опытом, музыканты больше не пытались выступать перед поклонниками традиционной музыки, вместо этого они стали искать одобрения среди аудитории группы «Apocalyptica». Трио выпускников Академии Сибелиуса дебютировали на одной сцене с "His Infernal Majesty". В то время никто и предположить не мог, что обе команды ждут мировая слава многомиллионные тиражи альбомов. Пока «Apocalyptica» были лишь начинающим симфоническим трио, игравшим кавер-версии «Metallica». В 2004 году группы продолжили сотрудничество: Вилле Вало и вокалист «Rasmus» Лаури Юлонен записали вместе с «Apocalyptica» сингл «Bittersweet». Но в далеком 1996-м, когда слава лежала ещё впереди, музыканты дали совместный концерт в небольшом хельсинкском клубе. Ребята были приятно удивлены и воодушевлены восторженной реакцией публики. Однако звучание группы заставило Вилле задуматься о необходимости хорошего клавишника.
Вопрос встал особенно остро, когда музыканты HIM собрались в студии для записи очередной демопластинки. В числе песен был хит Криса Айзенка "Wicked Game", возглавивший вершины чартов по обе стороны Атлантики после успеха фильма Дэвида Линча "Дикие сердцем". Чтобы добавить песне желаемый эффект звука проливного дождя, Антто Эйнари Меласниеми приготовил специальные сэмплы. Антто нередко принимал участие в выстеплениях и студийных работах группы, пока в 1997 году не примкнул к HIM на постоянной основе.
Это была вторая демозапись "His Infernal Majesty". Помимо кавер-версии знаменитой песни Айзенка, в состав диска входили две оригинальные композиции: "Stigmata Diaboli", позже переработанная и включенная под названием "Sigillium Diaboli" в американское и немецкое издания альбома "Razorblade Romance", и "The Phantom Gate", слова которой послужили основой текста песни "Your Sweet 666", записанной в 1997-м.
Ошибки не совершают просто так, всегда есть причина. Поэтому каждый раз приходится совершать новые прекрасные ошибки.
Третье выступление "His Infernal Majesty" прошло все в том же клубе «Teatro» в апреле 1996 года. Программа состояла из каверов композиций шок-рокера Кинга Даймонда. Два месяца спустя ребята сыграли перед тысячной аудиторией, выступая на разогреве у группы «Jimsonweed». К тому времени четверка Вилле, Линде, Миге и Патка чувствовали себя достаточно уверенно, исполняя свои собственные треки наряду с кавер-версиями хитов "Type O Negative", «Kiss» и "W.A.S.P.". Именно после удачного выступления "His Infernal Majesty" перед большой аудиторией ребята решили приступить к записи первого студийного альбома.
Осуществление затеи стало возможным благодаря одному из исполнительных продюсеров «BMG» в Финляндии, Аско Каллонену. Он наткнулся на демозапись "His Infernal Majesty" в стопке дисков, которые ежедневно приходили к нему в офис по почте. Продюсеру, в настоящий момент возглавляющему жюри финской версии шоу "Народный артист", понравилась кавер-версия "Wicked Game", он обратил внимание на глубокий тембр голоса Вилле Вало. Каллонен решил, что HIM идеально подходит для нового дочернего лейбла «BMG» "Terrier", поэтому он без промедления связался с музыкантами. "Неделю спустя ко мне в офис вошел странный, похожий на хиппи парень в нелепом меховом пальто, — рассказал продюсер корреспонденту журнала «Suosikki». — Он беспрерывно курил и на все мои вопросы отвечал либо "не знаю", либо "мне все равно".
Опытный продюсер и промоутер был немного шокирован нелюдимостью Вилле Вало, знакомство же с остальными членами "His Infernal Majesty" привело его в глубокое замешательство. "Басист ходил по улице в одних трусах, у кедов барабанщика отваливались подошвы, а гитарист вообще не проронил ни единого слова". Каллонен не был впечатлен индивидуальностью каждого из участников группы, однако "качественно новое сочетание романтики и саморазрушения", звучавшее в их песнях, было достаточным аргументом для заключения контракта на выпуск первого альбома.
В августе того же года "His Infernal Majesty" провели пять дней на культовой финской студии звукозаписи «Finnvox», работая над дебютным синглом из четырех песен. Открывшаяся в 1965 году студия «Finnvox» является финским аналогом знаменитой студии "Abby Road" в Лондоне. Запись продюсировал Хиили Хиилесмаа, один из участников группы "The Skreppers", которая впоследствии часто выступала на разогреве у HIM.
В сингл вошли песни "Wicked Game", "Stigmata Diaboli" и "The Heartless". Помимо них был записан трек "Dark Secret Love", вошедший в немецкое издание сингла "Join Me" в 1999 году. Все четыре песни наглядно показали, что музыкантам удалось на основе жестких рифов "Black Sabbath" создать оригинальное звучание благодаря использованию прозрачного многослойного бэк-вокала и плотных гитар. В записи принял участие гитарист трэш-металл-группы «Charged» по имени Оки, который значительно усилил партию ритм-гитары. Однако этому сотрудничеству не суждено было продлится долго. Оки влюбился в девушку Патки, что после взаимных разбирательств привело к исключению Оки из состава группы ещё до первого их совместного выступления.
Сингл "666 Ways To Love: Prologue" увидел свет 19 октября 1996 года. Диск выпустили тиражом 1000 экземпляров и разослали работникам сферы массовой информации, музыкальным критикам и ведущим радиостанций. На обложку была помещена фотография матери Вилл, Аниты Вало, снятая в шестидесятые годы. Для оформления внутренней стороны вкладыша использовались фотография Вилле и снимок всей группы.
Музыканты отметили свой первый релиз концертом в клубе «Tavastia». Финские радиостанции пустили в жесткую ротацию готическую версию "Wicked Game". Несмотря на ограниченное число копий, сингл достиг первой десятки национального музыкального хит-парада и продержался там до конца года. Антто срежессировал и снял на любительскую видеокамеру клип на песню. По сюжету, музыканты выгуливали в парке собаку. Однако до выхода на DVD видеоматериалов "Love Metal Archives. Volume 1" широкой публике увидеть клип было не суждено. Выбор песни для кавер-версии Вилле Вало объяснил в интервью телеканалу "Kerrang!": в то время мы играли множество каверов разных исполнителей, от Мадонны до «Ramones». Нам очень понравилась эта песня, она просто потрясающая и подходила нам по звучанию и смыслу".
Наш барабанщик может говорить только о своей барабанной установке, клавишник — о танцевальной музыке и техно-культуре, а гитарист вообще немой!
По традиции, взявшей свое начало от первого живого выступления группы, HIM отыграли свой последний в 1996 году концерт в новогоднюю ночь на уже знакомой им площадке клуба «Teatro». Музыканты исполнили песни "Depeche Mode", Раули Самерйоки и других классиков поп-сцены. На разогреве выступили «Rasmus» и прогрессив-металл-группа «Kyyria», чей барабанщик примкнул к основному составу HIM спустя два с половиной года. Успех новогоднего концерта привлек внимание специалиста по связям с общественностью Силке Юли-Сирнио. Она прокомментировала выступление Вилле словами: "Это что — реинкарнация Джима Моррисона?" Силке имела обширные связи в немецкой музыкальной индустрии и представляла компанию "Drakkar Entertainment", в свою очередь связанную с успешной звукозаписывающей фирмой «BMG» в Германии. Она предложила музыкантам контракт с немецким отделением корпорации.
Так к успеху на родине прибавились антураж и менеджмент, необходимый группе, чтобы прославиться в Европе. Помимо Силке и Аско Каллонена, к менеджменту группы примкнула Тина Вуринен, известная организацией концертных туров по Европе других популярных групп Скандинавии. Именно она помогла музыкантам организовать их первые гастроли. "Поначалу я не знал, что она за фрукт, — смеется Вилле. — Она производила впечатление знающего человека, но при этом жутко воображала!" Тина была бывшей женой менеджера "Hanoi Rocks" Сеппо Вестеринена, который сразу заинтересовался HIM после посещения их концерта в июне 1997 года.