Le groupe signe son premier contrat d'enregistrement avec le label allemandMotor Music le [7] et entre dès le dans les Studios Polar à Stockholm pour commencer l'enregistrement de son premier album. Après de longues recherches pour trouver un producteur, le groupe arrêta son choix sur Jacob Hellner qui avait déjà travaillé sur les albums du groupe suédois Clawfinger, et sera assisté de Carl Michael Herlöffson. De nombreux conflits d'ego émaillèrent l'enregistrement, Hellner préférant travailler avec Till Lindemann, il écartait parfois les autres musiciens du studio [8]. Lorsque la situation devint insoutenable, le groupe rentra en Allemagne et l'album fut mixé par Ronald Prent dans les studios H.O.M.E. (anciennement Château du Pape, nom noté dans le livret de l'album[9] ) dans la ville de Hambourg.
Polémique
Aux États-Unis, ce premier album de Rammstein est sorti le avec une pochette différente pour couper court aux allégations de message néo-nazi contenu dans la photo de couverture, qui montre les six membres torses nus, tous muscles saillants (Pochette initiale / Pochette américaine), les médias allemands comparant cette photo à un poster pour promouvoir une « nouvelle race supérieure ». De plus un critique trouvait que la façon dont Till Lindemann roule les R en chantant est comparable aux discours d'Adolf Hitler[10]. En France, le livret d'Herzeleid comprend la traduction des paroles en français, pour bien montrer que le groupe ne véhicule pas de tels discours.
Singles
La sortie de l'album sera précédée par le single Du riechst so gut (qui fera aussi l'objet d'un clip vidéo) le [11]. Ce titre sera remixé et ressortira en maxi-single sous le titre Du riechst so gut '98 le , accompagné par huit remix différents faits par des artistes tels que Günter Schultz, Sascha Konietzko de KMFDM, ou Faith No More, et un nouveau clip vidéo. Il atteindra la 16e place des charts allemands[12].
Deux autres chansons sortiront en single, Seemann (accompagnée d'un clip) le , et Asche zu Asche, le . Ce dernier sortira sous forme d'EP 6 titres uniquement en Australie afin de promouvoir la tournée Big Day Out / Club tour 2001 que le groupe fit en janvier et en Nouvelle-Zélande et en Australie. Il sortira en version deux titres en Allemagne et au Mexique,mais uniquement à des fins promotionnelles[13].
Tournées
Rammstein commença la promotion de son album en partant en tournée à partir du avec le groupe allemand Project Pitchfork pour 17 concerts en Allemagne. Puis en première partie de Clawfinger à Varsovie et Prague () et en Autriche et Suisse (). Le groupe effectua sa première tournée en tête d'affiche en Allemagne du 2 au [14]. En , le groupe fait la première partie de la tournée d'adieu allemande des Ramones (8 dates), avant d'effectuer deux nouvelles tournées allemandes qui les occuperont une grande partie de l'année 1996.
Réception
L'album fit sa première apparition dans les charts allemands le , il occupait la 99e place[15]. Il navigua ensuite dans les charts pendant 102 semaines jusqu'en [16], atteignant une 6e place le [17]. Il fit aussi son apparition dans les charts des pays frontaliers de l'Allemagne, Autriche, Suisse, Pays-Bas. En France il se classa à la 85e place, mais seulement en 2005[18].
Le , Herzeleid fut certifié disque d'or en Allemagne[19] et le , le groupe se verra remettre un disque de platine. En 2005, Rammstein se voit remettre un "IFPI Platinum Europe Award" ce qui équivaut à la vente de plus d'un million d'albums en Europe.
Alors que le groupe cherchait un réalisateur pour le clip vidéo de Seemann, leur manager Emanuel Fialik envoya un CD de Herzeleid au cinéaste américain David Lynch, dont les membres du groupe sont des fans de longue date, en espérant attirer son attention [8]. Celui-ci n'y prêta pas attention tout de suite, ce n'est que lors d'un trajet en voiture pour se rendre en repérage à la Vallée de la Mort, qu'il l'écouta, et dès la première écoute, il réalisa que c'était exactement la musique qu'il recherchait pour son prochain film, Lost Highway. Les titres Heirate Mich et Rammstein figureront sur la BO du film[20].
Lynch passait Herzeleid à un volume très élevé au travers de deux énormes haut-parleurs alors qu'il tournait une scène du film (celle du couloir de la mort), mais pas seulement, il le passait aussi pendant les pauses. Henry Rollins, qui a un rôle dans le film, reporta que les personnes qui étaient présentes sur le plateau se mettaient à danser, ravies par la musique. Finalement, la société de production de Lynch (Asymmetrical Productions) commanda plus de 70 exemplaires de Herzeleid pour les membres de l'équipe de tournage[20].