Après beaucoup d'efforts, de répétitions et de nuits blanches, Rammstein met en boîte sa première démo. En 1995, le groupe est enfin prêt à produire quelque chose de brut. Emu, le manager de Rammstein met en place leur premier contrat d 'enregistrement, en faisant signer le groupe avec la maison de disque Motor. C'est également à cette période que les six allemands commencent à réellement travailler sur leur premier album. C'est difficile de trouver un producteur lorsqu'on débute, et particulièrement lorsqu'on explore de nouvelles voies. Après plusieurs mois de recherches, le groupe rencontre Jacob Hellner, un suédois qui paraît travailler sérieusement, lors d'un concert à Hambourg.
Rapidement, Jacob invite Rammstein au Polarstudio de Stockholm, l'ancien studio du groupe Abba. Le groupe loge dans deux appartements, un en centre ville et un autre en périphérie. Tout est nouveau pour eux qui n'ont jamais eu l'occasion de travailler dans de telles conditions.
Des tensions apparaissent vite au sein du groupe. Chacun veux se mettre en avant, et tout est une question de force, de compétence et de hiérarchie. Jacob Hellner préférait travailler avec Till, allant même parfois jusqu'à l'écarter des cinq autres. Ca n'a bien sûr pas fonctionné. Rammstein n'est pas un groupe d'individualité, mais un groupe qui forme un tout. Selon Richard, ce fût le passage le plus dur qu'a eu à endurer Rammstein. C'en était arrivé à un tel point que la production de l'album fût stoppée. Les six allemands sont donc retournés à Berlin, et se sont remis en question. Finalement, les passages enregistrés à Stockholm furent mixés à Hambourg, et Herzeleid vit enfin le jour.
C'est d'abord le single Du riechst so gut '95 qui débarque dans les bacs le 17 Août 1995. Il est accompagné d'un clip tourné avec très peu de moyen et sans réalisateur.
Un mois plus tard, l'album tant attendu Herzeleid est disponible chez les disquaires. Le nom Herzeleid (peines de coeurs) vient de la situation maritale des membres du groupe. Tous à peu près sont divorcés ou remariés.
Herzeleid ravit le public métal germanique mais a du mal à traverser les frontières à cause de la langue, des riffs durs et d'une sorte d'image bestiale voire même sanguinaire que dégageait le groupe selon les autres pays. En effet, les membres ont été accusés d'appartenir à la mouvance néo-nazie à cause de la pochette de Herzeleid ! En effet certains y voyaient le Herrenvolk (la race des seigneurs) prônée par Hitler...Idée totalement stupide. Le groupe a simplement choisi cette photo à cause de l'esthétisme qu'elle dégageait. Mais avec le recul, le groupe préfère quand même changer de pochette pour l'édition américaine d'Herzeleid.
Qu'importe, le premier album de la formation allemande se classe parmi les meilleures ventes et devient même disque de platine en quelques semaines.
Le succès de l'album pousse le groupe à enchaîner les tournées en 1995. D'abord en première partie de Project Pitchwork en Octobre pour une quinzaine de concerts, puis en première partie Clawfinger en Novembre, Rammstein se paye sa première vraie tournée allemande en tant que tête d'affiche à partir de Décembre 1995.
Le 8 Janvier 1996, c'est Seemann, le second single tiré d'Herzeleid, qui sort. Le groupe, qui espère tourner un clip un peu plus abouti que Du riechst so gut '95 préfère faire confiance eu professionnalisme d'un réalisateur. Les six allemands proposent donc au réalisateur américain David Lynch de les aider. Sans trop d'illusions, Emmanuel Fialik envoie donc un CD d'Herzeleid à Lynch, en espérant au pire qu'il choisisse un morceau pour la BO de l'un de ses films. Sans réponse de David Lynch, le groupe décide de travailler avec Lazlo Kadar. Ce choix porte ses fruits, puisque les premiers clips proposent un univers intense qui accroît encore la popularité de Rammstein.
Alors que le groupe repart en première partie de la tournée d'adieu des Ramones et multiplie les concerts, Herzeleid atterrit enfin sur le bureau de David Lynch, justement en train de finaliser son dernier film, Lost Highway. En écoutant le disque, il est immédiatement conquis par la musique allemande et décide d'apporter à la BO du film les chansons Rammstein et Heirate mich.
Le groupe, qui n'a pas eu de nouvelle de Lynch pendant près d'un an apprend la présence des titres sur la BO grâce à une lettre postée à l'en-tête de la maison de production du réalisateur. Lorsque les six allemands voient Rammstein et Heirate mich figurer sur la liste, ils sont fous de joie.
Après une longue tournée allemande, Rammstein s'apprête à livrer son premier très gros concert le 27 Septembre 1996. Le groupe a en effet organisé un concert de jubilé à L'Arena de Berlin : le "100 Jahre Rammstein". On retrouve sur scène Moby, l'orchestre philharmonique de Berlin et la chanteuse Bobolina, amie du groupe et présente sur la version studio de Engel. C'est également le premier concert pendant lequel le groupe met en place la grosse partie des effets pyrotechnique qui deviendront ensuite des classiques. Le concert est filmé, et une cassette VHS sera même distribuée aux membres de la Fanarea.
