Группа приступила к записи альбома в Polar Studios в Швеции. В течение примерно двух недель группа и их продюсеры, Якоб Хелльнер и Карл-Михаэль Херлёфссон, записали большую часть партий барабанов и баса, а также некоторые гитарные партии. Кроме того, они работали с компьютером, для того, чтобы сэмплировать гитары и создавать сэмплы звуков. Покинув Polar Studios, все они отправились в частную студию Якоба и Карла-Михаэля. Во время работы в новой студии они записали гитары и сделали дополнительные записи. Вокал также записывался в новой студии, где Тилль работал только с Якобом, в то время как Карл-Михаэль больше занимался программированием и сэмплированием. Во время этих записей группа хотела, чтобы строчка «Der Wahnsinn» звучала так, как если бы она звучала из телефона. Поэтому один из участников группы вышел в метро Стокгольма, одетый только в белую футболку, подтяжки, ботинки и короткие штаны. Из метро он позвонил в студию и повторил строчку «Der Wahnsinn» снова и снова в разных интонациях. Вдруг он услышал, как кто-то рядом с ним звонит в полицию и говорит, что какой-то сумасшедший кричит в трубку немецкую чушь.
Первый микс, который был сделан Хелльнером и Херлёфсоном, был сделан в MFG Studios. Рихард был единственным участником группы, который присутствовал при первых сессиях микширования. Но он не был удовлетворён тем, как всё обернулось, и позвонил всем остальным участникам группы, менеджменту и лейблу. Вместе они решили, что им нужен другой человек для работы над записью, и так они остановились на Рональде Пренте. Когда лейбл связался с Рональдом, он был в отпуске на острове Крит в Греции. После этого он поговорил с Якобом, который также находился в Греции в то же время. Вместе они отправились в Гамбург и попробовали свести альбом в Chateau du Pape Sutdios. Во время новых сессий присутствовала вся группа. Они решили начать с одной песни и сделать как можно больше миксов. Каждый раз, когда был сделана новая версия, группа выходила из студии и обсуждала её на улице. Однажды они захотели, чтобы песня была сведена таким образом, чтобы она звучала как у Bon Jovi, услышав результат, они отклонили эту версию. Однажды Рональду пришла в голову идея использовать определенный тип компрессии, который сделал бы музыку более сухой и «in your face». Услышав этот микс, группа коллективно согласилась, что это именно то звучание Rammstein, которое они хотят.
До того, как альбом получил название Herzeleid, он носил названия Rammstein и Heirate mich.
Первое пресс-прослушивание альбома состоялось в студии Chateau Du Pape. Музыкальный журналист Маттиас Минер был приглашен Motor Music послушать песни и посмотреть, действительно ли группа может стать следующим большим открытием. Четыре недели спустя группа провела открытую пресс-конференцию в кинотеатре "Blow Up" в Берлине. На экране показывали черно-белый немой фильм, и группа сидела cреди остальных людей в зале кинотеатра, а не перед журналистами, сидевшими в первом ряду. Группа всегда отвечала слева направо, независимо от того, кого спрашивали.
Якоб Хелльнер упомянул в интервью, что в общей сложности группа записала 18 песен за шесть недель.
Сначала грядущий альбом продвигался тремя разными кассетами: 3-Track Demo,6-Track Demo, 6 Rough Mixes. Все они были разосланы Motor Music. После того, как альбом и первый сингл Du Riechst So Gut были выпущены, вышла вариация альбома в так называемом "Riech!"-боксе. Бокс включал в себя альбом (иногда только сингл, иногда и то, и другое), маленький флакон духов "Obsession" от Calvin Klein и несколько различных наборов рекламных листовок об альбоме.