PERZONAL WAR основана Matthias Zimmer (вокал; гитара), Martin Buchwalter (барабаны), Sascha Kerschgens (гитара) и Frank Buchwalter (бас) в 1996 году. После выпуска пары демо в 1998 году группа записала дебютный альбом "The Inside", который собрал отличные рецензии в европейских журналах.
          В начале 2000 года группа записала второй альбом "NewtimeChaos", который вышел в мае того же года. В марте 2002 года Personal War сменили название с "Personal War" на "Perzonal War" из юридических соображений и подписали контракт с фирмой AFM-Records. В июле 2002 года записан третий альбом "Different But The Same" и издан фирмой AFM Records. Victor Smolski из RAGE сыграл пару гитарных соло для этого альбома и помог музыкантам в студийных работах.
          После множества концертов и выступлений на фестивалях (к примеру, на Sziget Festival в Будапеште, разогревая RAGE и NEVERMORE) в январе 2003 года басист Frank Buchwalter ушел из группы. В июне 2003 года PERZONAL WAR снова отправились в студию, чтобы записать альбом "Faces". Уже во время записи басист Sven Krautkraemer присоединился к коллективу и сделал PERZONAL WAR сильнее, чем они когда-либо были. Группа также сняла клип на песню "My Secret" с популярными немецкими операторами и режиссерами. После этого был дан успешный тур с "Circle to Circle" и "Blaze". "Faces" получился сильнее своих предшественников (Rock Hard Germany поставили 10 баллов, 7 позиция в Metal Hammer Germany Soundcheck).