У 1985-му році Ернст Хорн, піаніст, ударник і диригент з Мюнхена розмістив оголошення в газеті про пошук "вокаліста, якому б подобалося експериментувати". Таким чином, він познайомився з Олександром Вельяновим, який приїхав до Мюнхена з Берліна вчитися кіно і театрального мистецтву. Разом вони сформували "Deine Lakaien", запозичивши назву з однієї пісні "Einsturzende Neubaten".
Через рік на власні гроші хлопці випустили дебютний альбом. Поки запис пробивала собі шлях на незалежну клубну сцену, самі музиканти працювали над іншими проектами. У 1990-му "Deine Lakaien" привернув увагу "Gymnastic Records". Заручившись контрактом, дует створив другий альбом, прийнятий з великим ентузіазмом.
Пісні "Dark Star", "Reincarnation" і "Love Me To The End" стали гарантією заповнення танцмайданчиків. Це полумечтательное, полуагрессівное нойз-поп-звучання з глибоким теплим вокалом стало фірмовим стилем "Deine Lakaien". Також у 1991-му вийшов міньйон "2nd Star", на якому були присутні як нові пісні, так і ремікси з "Dark Star". Після перевидання дебютного альбому "Deine Lakaien" зробили свій перший концертний тур, для якого запросили ще двох музикантів: Крістіана Коморовського (скрипка) і Майкла Поппа (скрипка, електрогітара, шарманка).
На подив шанувальників "Deine Lakaien" переробили для цього туру всі свої пісні, презентуючи публіці чудовий синтез живих електронних і класичних інструментів і вокалу. Через безперервні прохань публіки "Gymnastic" на основі "Dark Star Tour" випустили концертний альбом "Dark Star Live". Подальші гастролі значилися як "The Dark Moon Tour", причому "Deine Lakaien" грали свої пісні в акустичному варіанті - лише піаніно і вокал. Як і раніше, всі концертні зали та майданчики були заповнені вщерть. У наступному році група з'явилася на фестивалях "Noise Now" і "Zillo Open Air", а також виконала акустичну програму в якості гостей на концерті Ніка Кейва.
Дворічний простий в студійній роботі був перерваний виходом альбому "Forest Enter Exit", яка зробила "Deine Lakaien" феноменом серед європейських електронних груп. У 1994-му також вийшов міньйон "Mindmachine" і однойменний кліп, знятий Ніко Байєром. На наступний рік за мотивами чергового туру був виданий альбом "Acoustic", відразу ж потрапив у німецький хіт-парад і протримався там кілька тижнів. Черговий студійний альбом з дивною назвою "Winter Fish Testosteron" вийшов у 1996-му разом з другим кліпом, "Away".
Відкатавши аншлагові гастролі з новаторським авангардним проектом "Qntal" і засвітившись на декількох великих фестивалях, музиканти вирішили трохи призупинити спільну діяльність. Цей час вони присвятили сольним проектам, після чого почалися приготування до запису "Kasmodiah". Цього разу в сесіях брали участь Майкл Попп і Крістіан Коморовський. У новому році "Deine Lakaien" уклали угоду про співпрацю з "Columbia Records", що принесло групі додатковий комерційний успіх. Багато в чому завдяки "мажорному" лейблу "Kasmodiah" відразу ж після виходу потрапив на 4-у сходинку німецьких чартів. Дві наступні студійні роботи з'явилися з інтервалом у три роки.
У створенні "April Skies" брали участь музиканти з туру "White Lies": Дойтунг (віолончель), Іві Леон (скрипка, бек-вокал), Шаріфа (скрипка, бек-вокал) і Роберт Вількокс (гітара, клавішні). Завдяки цьому альбом вийшов більш живим, більш екстремальним і більш сильним. Також можна було помітити деякі зміни з концептуальної сторони: гітари стали домінуючими, а використання струнної секції і жіночого бек-вокалу визначено додало музиці фарб.