Саундтрек до фільму Девіда Лінча Lost Highway з двома піснями гурту вийшов наприкінці 1996 у США, та навесні наступного року в Європі. Rammstein знову поїхали в тур — цього разу не лише Німеччиною, а й Австрією та Швейцарією. 27 вересня зіграли концерт 100 years of Rammstein, де як гості з'явилися Мобі, Berlin Session Orchestra та інші. Ідеї для нового альбому не давали спати, то ж, вже в листопаді гурт вирушив до Мальти на запис у славнозвісній Temple Studios. Перший сингл, Engel, приніс Раммштайн перший "золотий" статус, а альбом Sehnsucht підніс їх на перші сходинки німецьких чартів. Попереду були солдаути в Європі та перші виступи в Америці.
