Дебютний альбом, Herzeleid, гурт почав записувати в березні 1995. Вже в серпні видали перший сингл, Du riechst so gut, а за місяць, власне, платівку. Rammstein поїхали на концерти до Праги та Варшави разом із Clawfinger. А вже в грудні того ж року проїхалися з 17-ма хедлайн-шоу Німеччиною. Ці концерти зробили їх популярними вдома та закріпили за гуртом славу крутого лайв-бенду. В березні 1996 музикантів побачили в програмі лондонського MTV "Hanging Out" — це стало для Rammstein першою британською появою. А перший потужний спалах успіху по за межами Німеччини чекав на музикантів незабаром. Вони відчули його, коли фронтмен Nine Inch Nails Трент Резнор обрав дві їхні пісні, Heirate mich та Rammstein під час створення саундтреку до стрічки Девіда Лінча Lost Highway.
