Группа была создана в 1982 году под названием Knight of Demon в городе Лёррах. Изначальный состав включал басиста и вокалиста Марселя Ширмера (также известного под псевдонимом Шмир), барабанщика Томми Зандманна и гитариста Майка Зифрингера. Вскоре после своего образования группа сменила название на Destruction и сделала две демо записи. В том же составе были записаны первые два альбома и проведено турне по Германии на разогреве у Slayer. В 1988 году был выпущен Release from Agony, получивший несколько противоречивые оценки в прессе. На этом же альбоме сыграли новые участники группы — второй гитарист Гарри Вилкенс и ударник Оливер «Олли» Кайзер, которые пришли годом раньше. Следующим релизом группы стал концертный альбом Live Without Sense.
В 1989 году из-за, в большей степени музыкальных, нежели иных разногласий с другими участниками группы состав покидает Марсель Ширмер. Проблемы между участниками начались ещё в период сочинения музыки и Ширмер, ввиду несоответствия нового материала его музыкальным предпочтениям, был изгнан из состава. Ширмер основал свою группу Headhunter, в которую, помимо прочих, вошёл Йорг Михаэль. Уже без него был записан новый альбом Cracked Brain (1990), после которого группа потеряла поддержку лейбла Modern Music. В качестве вокалиста на релизе сессионно выступил вокалист группы Poltergeist André Grieder, также сессионно был привлечён и басист Christian Engler. В 1998 году группа самостоятельно выпустила альбом The Least Successful Human Cannonball не вошедший в официальную дискографию, на котором вокальные партии исполнил Thomas Rosenmerkel. На этом альбоме группа сменила направление от трэш-метала в сторону грув/фанк метала. В 1999 году в группу вернулся Марсель Ширмер и был подписан контракт с Nuclear Blast, на котором было выпущено три последующих альбома. Воссоединение группы в почти классическом составе долгое время не поддерживалось ни Майком Зифрингером, ни самим Шмиром, но однажды они всё-таки, при главенстве в этом вопросе желания поклонников, решили играть вместе. Альбомы Inventor of Evil (2005), Thrash Anthems (2007) и D.E.V.O.L.U.T.I.O.N (2008) вышли на лейбле AFM Records. Новый альбом Destruction решили назвать Day Of Reckoning. Он вышел в январе 2011 года на лейбле Nuclear Blast Records. В 2012 году Destruction записали свой юбилейный альбом „Spiritual Genocide” в честь 30-летия коллектива, который вышел в ноябре на Nuclear Blast Records. Микшированием занимался Andy Classen, а в качестве гостей на диске приняли участие Thomas "Angelripper" Such (Sodom), Andreas "Gerre" Geremia (Tankard) и Ol Drake (Evile). Кроме того, ради одной песни Destruction собрались в составе, известном по альбому „Release From Agony” — с гитаристом Harry Wilkens'ом и барабанщиком Oliver'ом "Olly" Kaiser'ом.
