Так появился другой кандидат: шведский продюсер Якоб Хелльнер прибыл по приглашению менеджера группы в декабре 1994 года в Гамбург на концерт Rammstein. Ранее Хелльнер хорошо зарекомендовал себя в работе с успешной метал-группой Clawfinger. Хелльнеру настолько понравилось выступление Rammstein, что он не раздумывая согласился выпустить их альбом, который позднее продавался в каждом музыкальном магазине под названием Herzeleid.

Пусть и незапланированно, но Rammstein и Якоб нашли друг друга. Группа отправилась в Стокгольм в студию звукозаписи. Там был записан их дебютный альбом Herzeleid, с которого началась настоящая история успеха, о котором никто из причастных не мог и мечтать…

24 сентября 1995 г. в продажу вышел Herzeleid – первый альбом Рихарда Круспе, Кристиана «Флаке» Лоренца, Тилля Линдеманна, Оливера Риделя, Кристофа Шнайдера и Пауля Ландерса – коллектива Rammstein. Однако путь к готовому дебютному альбому оказался очень неровным и тернистым.

После того, как секстет наконец нашёл в лице Якоба Хелльнера подходящего и увлечённого продюсера, возникли первые проблемы. Песни для Herzeleid должны были записываться в студии Polar Studios в шведской столице, которая создавалась для поп-группы ABBA.

Но производство альбома затянулось. Сперва группа целую неделю отрабатывала партию ударных. Затем музыканты отправились в студию Хелльнера, что ещё больше усложнило ситуацию, как рассказал гитарист Рихард Круспе британскому журналу Metal Hammer в выпуске 05/06: «Мне было там непросто найти подходящее гитарное звучание. Места было недостаточно, и помещение очень сильно отличалось от тех, в которых я привык репетировать. Нужно было по-настоящему перестроиться, но мне такая перемена не понравилась. Для нас было проблемой и то, что мы застряли в Стокгольме. Якоб работал только в определённые часы. Поэтому по вечерам и на выходных мы были предоставлены сами себе. Мы не говорили по-шведски, а по-английски – недостаточно хорошо, и чувствовали себя из-за этого некомфортно. Мы не могли никуда пойти и не могли ничего предпринять. Поэтому у нас был не лучший настрой».

Но на этом трудности не закончились. Когда Якоб Хелльнер начал работать с Тиллем над вокалом, шестёрка музыкантов заметила, что поскольку продюсер практически ничего не понимал по-немецки и уж тем более не говорил на языке, он не мог понять о чём идёт речь в песнях. Каким образом он в таком случае мог работать с их материалом и придать содержанию песен подходящую музыкальную форму? В вышеупомянутой статье Metal Hammer Рихард описывает состояние секстета в той ситуация как «очень, очень подавленное».

Тем не менее группа продолжала работу с продюсером над альбомом на протяжении трёх месяцев. Они репетировали, шлифовали песни и делали записи до тех пор, пока не пришло время сводить треки. Рихард вспоминает об этом в Metal Hammer: «Мы поручили это Якобу. А почему нет? Он же всё записал. Но это оказалось огромной ошибкой с нашей стороны. Я был единственным из группы, кто присутствовал при начале сведения. Вскоре я понял, что Якоб не ведал что творил. Мы начали спорить, работа не продвигалась, я был очень недоволен. Но что я мог сделать?»

В этой ситуации Рихард решил созвать экстренное совещание с коллегами по группе, Якобом Хелльнером, менеджером группы Эмануэлем Фиаликом и представителями из звукозаписывающей компании Motor Music. Встреча состоялась в Берлине, по результатам которой производство альбома начало двигаться в правильном направлении. Первым делом от работы был отстранён звукооператор и ассистент продюсера Карл-Михаэль Херлоффсон, который по причине серьёзных проблем в личной жизни пренебрегал работой над песнями Rammstein в студии. Его заменил Рональд Прент из Нидерландов. В итоге он закончил сводить записанные в Стокгольме песни в Гамбурге. Рихард высоко отзывается о работе Рональда в вышеупомянутой статье в Metal Hammer: «Надо сказать, что с Рональдом было непросто работать. Наши мнения порой расходились. Но он действительно спас альбом. Мне страшно подумать, что бы произошло, не подключись он к работе!»

В конце концов на последней стадии производства альбома отношения между группой и продюсером наладились. Гитарист Пауль Ландерс рассказал об этом в интервью журналу Rock Hard в выпуске 06/04: «Он, равно как и мы, вынес из этого урок и сделал всё, на что он на тот момент был способен. Как он, так и мы достигли тогда предела наших возможностей». Рихард тоже вскоре помирился с Якобом Хелльнером. Позднее, в декабре 2005 г., он высоко отзывался о нём в интервью музыкальному интернет-порталу apple.com: «Я очень ценю работу нашего продюсера. Он видит то, что скрыто у тебя внутри, понимает это и пытается вытащить максимум из этого наружу, не пытаясь при этом тебя сломать. Для него важна каждая деталь, и он может услышать то, что никто другой не услышит. Я даже не могу вам сказать, что это, поскольку я тоже не могу это услышать».

Недостаток знаний немецкого языка Хелльнеру удалось превратить в своё преимущество: при производстве всех последующих альбомов он работал с голосом Тилля Линдеманна как с инструментом. С самого начала он был поражён, насколько точно фронтмен Rammstein при фразировке попадает в такт. Таким образом шведский продюсер мог очень ритмично встраивать голос Тилля в песни и даже более того: органично вплетать его в музыку.

Лучшим доказательством тому, что такой подход к Rammstein работал, является результат их сотрудничества в альбоме Herzeleid: звучание, которого добились группа и продюсер, не существовало прежде в немецкой рок-музыке. Rammstein объединили в Herzeleid суровые, жёсткие гитарные аккорды и мелодии баса с тяжёлым и острым ритмом, обеспечивавшимся ударными. Это дополнялось электронным звучанием, создававшим основу для ритмического рисунка и одновременно смягчавшим его. Мелодии синтезатора обволакивали этот тяжёлый каркас и по-настоящему облагораживали песни. Такая смесь из метала и электроники сильно отличала Rammstein от традиционных хеви-метал групп, таких как Iron Maiden, Judas Priest и в особенности Metallica. Она даже делала их музыку танцевальной, что на тот момент было верным решением, поскольку чеканные, пульсирующие ритмы техно были тогда в моде, и их влияние чётко прослеживается в Herzeleid. Поэтому стиль дебютного альбома можно охарактеризовать как грубый танцевальный метал, который они усовершенствовали в последующих пластинках, ставший позднее отличительным признаком Rammstein.

Другой характерной особенностью песен был вокал Линдеманна. Он интонировал песни глубоким, проникновенным басом или баритоном. Иногда он даже пел в диапазоне альта, как, например, в пятой песне альбома – Seemann, музыку для которой написал басист Оливер Ридель, впоследствии доработанную для Herzeleid Эммануэлем Фиаликом и Олафом Бруном. В 2003 году Нина Хаген и финский коллектив Apocalyptica, известный исполнением на виолончелях песен в стиле метал, сделали кавер на песню Seemann, достигший 13-й позиции в немецких сингл-чартах.

Отличительной особенностью вокала Тилля – а таким образом и ещё одной характерной чертой Rammstein – стала его раскатистая «р». Критики немедленно связали его пение с манерой речи видных ораторов времён третьего рейха, таких как рейхсминистр по пропаганде Йозефа Геббельса и прежде всего сам «фюрер» Адольф Гитлер, скандировавшие свои громогласный речи с похожими интонациями и такой же раскатистой «р». Такая ассоциация стала поводом определить секстет в правый конец политического спектра.