Тоді Пабло, Торстен і Волкер зайнялися пошуками підходящого вокалера, причому було вирішено, що їм потрібен не просто людина з мікрофоном, а справжній фронтмен.
Такий тип врешті-решт виявився в особі Йіоті Парчарідіса. Влітку 1999-го хлопці вирушили в Ганновер "Airport studio", де вже під ім'ям "Human fortress" записали новий демо. Випущене в форматі CD, воно викликало вкрай позитивні відгуки в ряді солідних німецьких металевих видань. Відповідно до команди проявили інтерес і деякі рекорд-компанії.
За весни 2000 року музиканти зібралися записувати чергову демку і зайнялися пошуком підходящої студії. Якраз в цей час їм підвернувся продюсер Томмі Ньютон, вже встиг завантажити з інтернету кілька композицій "Human fortress". Через пару днів після прослуховування пісень Ньютон зателефонував хлопцям, запросив у свою студію і запропонував довготривалу співпрацю. Хлопці відповіли згодою, і вже на початку літа команда сиділа в "Area 51 studio" і записувала свій перший альбом.
На початку 2001-го "Human fortress" взяли участь у міжнародному конкурсі, проведеному одним з провідних німецьких металевих журналів. За результатами цієї події їх композиція "The dragons lair" потрапила на відповідний збірник, а за опитуваннями відвідувачів веб-сайту вона була названа кращим треком.
Потім надійшла пропозиція від "Limb records", і у вересні 2001 року на цьому лейблі було видано дебютний альбом, "Lord of earth and heavens heir". Цей реліз заслужив схвальні відгуки, як у пресі, так і в вебзінах, що мають відношення до металу. Друга повноформатна робота "Human fortress" вийшла два роки опісля. Такий тривалий проміжок пояснювався переходом групи на інший лейбл. З "Limb records" у музикантів не склалися особисті відносини, і їм довелося піти під крило "Massacre records" (до речі, при цьому старий контракт залишився в дії). "Defenders of the crown" записувався в тій же "Area 51 studio" під керівництвом Томмі Ньютона і Паоло Мело.
На сесії в якості гостей були запрошені музиканти з дружніх команд - "Galloglass", "King Leoric" і "Meridian Zero". Альбом, заснований на сюжетах середньовіччя і рольових ігор, був зроблений в стилі павер-метал з епічними, гімновимі композиціями. Деякі фани навіть підібрали під нього своє визначення - "epic battle metal".