ארמילוס הוקמה ב-2000 בבית שאן. עפ"י האגדה היהודית, ארמילוס הוא שמו של המלך הרשע שיהרוג את משיח בן יוסף, יביא פורענות לעולם בטרם יוכרע ע"י משיח בן דוד, או אז תבוא הגאולה. הגיטריסט עידן אמסלם והמתופף מתן שמואלי, שניגנו יחד במספר הרכבים מקומיים (Metal INC, Generation P), חלמו על להקת דת' מטאל בסגנון של מורביד אנג'ל ודייסייד. בתחילת הדרך, אמסלם כתב את המילים לשירים. הסולן של הלהקה היה ניראל משה. החבורה החליטה לצרף גיטריסט קצב השולט במטאל, משימה לא פשוטה באיזור ההוא של המדינה, במיוחד בעידן הטרום-אינטרנטי. לאחר חיפושים נרחבים, הם מצאו את איתי זקש (לשעבר להקת Society victims). השיר הראשון שהקליטו נקרא "Satan's son".

לקראת הופעת הבכורה, צורף ללהקה הבאסיסט של להקת "בר מינן", לירן יום טוב. ניראל עזב את הלהקה חודש לפני הכניסה להקלטות. את משימת השירה נטל על עצמו זקש, ששיכתב מחדש שלושה שירים של הלהקה שיתאימו לסגנון החדש. שירים אלו מרכיבים את הדמו הראשון של הלהקה, Addicted.

באוגוסט 2001 הלהקה הופיעה לראשונה בפסטיבל אקסטרים-רוק בתל-אביב, שם מכרו את הדמו במספר עותקים מוגבל. שנה לאחר מכן, השתתפו בפסטיבל המטאל Embrace the dark, שם הציגו חומר חדש וברוטאלי יותר. מכיוון שסגנון הלהקה השתנה, הדמו כבר לא היה רלוונטי ולכן החליטו להקליט דמו חדש. בספטמבר 2002 נכנסו לאולפן ההקלטות של אייל גלוטמן (Betrayer, Eternal Gray) לחודש הקלטות. המאסטרינג בוצע ע"י מאור אפלבאום (Moonskin, Vultures).

לאחר הפסקה ארוכה, זנח איתי את תפקיד גיטריסט הקצב והתמקד בשירה. את מקומו תפס תומר פוקס, באסיסט להקת אלבא סולאריס. ההופעה הראשונה שלהם כחמישיה היתה ביום העצמאות 2003 בפסטיבל Metal till dawn. באותה תקופה הצטרפו שמואלי ויום-טוב לזמן קצר להרכב עזאזל. במקביל, החלו לעבוד עם Metalist productions על אי.פי ראשון, Race of Lies, שראה אור ב-2004. בהופעת ההשקה בחיפה השתתפו סיילם ואורח הכבוד נרגל, סולן להקת הדת'-מטאל הפולנית "Behemoth".