"Schmier" basszusgitáros/énekes, Mike Sifringer gitáros és Tommy Sandmann dobos alkotta zenekar 1984-ben vette fel a Destruction nevet, majd megjelentették első anyagukat, a nyers hangzású Sentence of Death mini-albumot. A debütáló Infernal Overkill (1985) és a második Eternal Devastation (1986) című albumokkal azonnal a német thrash metal élvonalába léptek. Európában már a Slayer előzenekarként trunéztak, és meghívást kaptak a montréaliWWIII metal-fesztiválra Kanadába.
1987-ben második gitárosként csatlakozott a zenekarhoz Harry Wilkens, majd egy doboscsere után Oliver "Olli" Kaiser. A Mad Butcher EP és a következő évben megjelent Release from Agony album már az ő közreműködésükkel készült el. Ezen a lemezen egy technikásabb, progresszívebb irányba mozdultak el, ami megosztotta a rajongókat. A katasztrofálisan sikerült Celtic Frost-al közös turné, és a Live Without Sense (1989) koncertalbum megjelenése után a frontember Schmiernek távoznia kellett.
Schmier Headhunter néven alapított új zenekart. A Destructionben a helyét az ex-Poltergeist énekes André Grieder vette át a mikrofonnál, míg a basszusgitáros Christian Engler lett. Az 1990-ben kiadott Cracked Brain című Destruction-albumra azonban nem volt kíváncsi a csalódott rajongótábor és a sikertelenség nyomán a zenekar gyakorlatilag feloszlott.
A gitáros Mike és a dobos Olli 1993-tól új énekessel (Thomas Rosenmerkel) dolgozott Destruction néven, bár az elkövetkező hat év hivatalosan nem számít a Destruction történetéhez, ahogy azt a zenekar honlapján megtalálható diszkográfiában is jelzik. Ezekben az években két EP (Destruction és Them Not Me címmel) és egy nagylemez (The Least Successful Human Cannonball) jelent meg szerzői kiadásban.
A Destruction ténylegesen 1999-ben alakult újjá, amikor Schmier visszatért. A kezdeti időkhöz hasonlóan a trió felállás mellett döntöttek. A Schmier (basszusgitár/ének), Mike (gitár) és az új dobos Sven Vormann alkotta Destruction a legnagyobb független metal-kiadóval, a Nuclear Blasttal kötött lemezszerződést. Rögtön neki is láttak egy új stúdióalbum felvételeinek, mely All Hells Break Loose címmel jelent meg az ezredfordulón. A klasszikus Destruction-hangzást megidéző lemezt a közönség és a szaksajtó egyaránt kedvezően fogadta. Az ekkor megszerzett pozícióját a következő albummal (The Antichrist, 2001) stabilizálni tudta a trió.
2002-ben Marc Reign lett a Destruction dobosa, de ez a tagcsere semmilyen törést nem okozott, azóta is rendszeresen jelentkeznek újabb lemezekkel. A zenekar megalakulásának 20 éves évfordulóját 2004-ben a Live DischargeDVD kiadásával ünnepelték, 2007-ben pedig a Thrash Anthems című albumon régi klasszikus dalaikat játszották fel újra modern hangzással. Utóbbi három lemezük - köztük a 2008-as D.E.V.O.L.U.T.I.O.N. - már az AFM kiadónál jelent meg. 2017-ben a Destruction új albumot fog megjelentetni, "Thrash Anthems II" néven, amely az előző részhez hasonlóan az együttes régi dalainak újra felvett verzióit fogja tartalmazni.
