Die Band wurde im Jahr 2000 von Sänger Tuberculosis, Gitarrist Kusmar, Schlagzeuger Rob Diver und Gitarrist Hardon gegründet. Zusammen nahmen sie innerhalb eines Tages ihr erstes selbstbetiteltes Demo. Im Anschluss mussten einige Mitglieder ihren Wehrdienst ableisten, was das weitere Voranschreiten der Band erschwerte. Im Jahr 2001 änderte die Band ihren Namen in Witheria und nahm in den Folgejahren die Demos Demo 02 und Pureditself auf.
Im Jahr 2004 Witheria nahm die Gruppe ihr erstes Promodemo in den Seawolf Studios auf. Jedoch konnte die Band dadurch keinen Plattenvertrag erreichen. Die Band nahm ein weiteres Demo, ehe sie sich in das Jive Studio begaben, um das Debütalbum Infernal Maze im Jahr 2005 aufzunehmen. Im Folgejahr wurde das Album über Twisted Face Records veröffentlicht. Es folgten Auftritte in ganz Finnland, während die Gruppe an ihrem zweiten Album Painful Escape arbeitete, das im Jahr 2007 im Jive Studio aufgenommen wurde. Der Tonträger erschien Anfang 2009 über Stay Heavy Records. Das Album wurde auf der Finnish Metal Expo beworben und es folgten diverse Auftritte, darunter auch einer in London. Im Jahr 2010 begab sich die Band in das D-Studio, um das dritte Album Vanishing Order aufzunehmen.[1] Das Album erschien im Jahr 2011 über Violent Journey Records.[2]
