Le groupe a été créé au Printemps 2001 par le chanteur/bassiste Jason Netherton et le chanteur/guitariste Mike Harrison en tant que projet studio, avec la batterie occupée par l'ex-batteur de Dying Fetus, Kevin Talley. "Overthrow", leur premier CD, fut publié en Septembre 2001 par la propre compagnie du groupe, Anarchos Records et attira rapidement l'attention et l'intérêt des cercles "underground" avec ses cinq excellentes chansons. L'album fut subséquemment publié au Japon en 2002 par Howling Bull/Ritual Records, et en Europe par Fadeless Records. Une édition limitée en vinyl fut également mise en vente par Goodlife Recordings peu après. Le groupe se transforma par la suite en un projet à temps plein avec l'addition de Sparky Voyles à la guitare.
Par après, la deuxième publication du groupe un EP partagé avec le groupe Commit Suicide de Pittsburgh sur Willowtip Records. Le CD présentait deux nouvelles chansons ainsi qu'une reprise de Disrupt et fut lancé dans l'Été 2002.
Après l'enregistrement d'un second EP en Mars 2002, Mike Harrison et Kevin Talley quittèrent le groupe pour continuer d'autres projets, et avec l'addition de Matt Byers à la batterie (ex-Severed Head), Misery Index partit pour sa première tournée des États-Unis pendant l'Été 2002.
Après ça, 2003 fut l'année où il publièrent un autre EP partagé avec le groupe Structure Of Lies, originaire d'Arizona, et où Misery Index lança son premier album complet pour Nuclear Blast, intitulé "Retaliate". Avec l'arrivée de Bruce Greig comme second guitariste, le groupe fit plusieurs tournées pour faire la promotion du nouvel album, qui fut lancé le 26 Août 2003.
Subséquemment, en 2004, le groupe s'embarqua dans plusieurs tournées aux États-Unis et en Europe pour présenter "Retaliate", enregistrèrent un vidéoclip pour la chanson "The Great Depression" et publièrent leur tout premier DVD, qui présente un concert complet en Grèce, encore une fois sur leur propre compagnie Anarchos Records. Avec l'arrivée d'Adam Jarvis à la batterie en Août 2004, le groupe fit quelques prestations aux festivaux Wacken, Brutal Assault et Party San, pour ensuite enregistrer le EP "Dissent" en Été 2004. "Dissent" représente la nouvelle naissance de Misery Index, poussant encore plus loin la sonorité de "Retaliate".
Le groupe fit encore des tournées intensives pendant l'Hiver 2004 et le Printemps 2005 pour supporter leur EP, et ils firent quelques prestations aux côtés de groupes comme Napalm Death, Suffocation, Behemoth, Neuraxis, Rotten Sound, Magrudergrind et Devil Inside. En Février 2005, le groupe vit l'arrivé de Mark Kloeppal, surnom Lo Sneek, en tant que second guitariste et vocal, qui s'occupa de paufiner encore un peu le son du groupe.