Il gruppo nacque a Krosno, nel sud della Polonia, nel 1996, quando l'età media dei componenti era di soli 14 anni e tutti i componenti frequentavano il conservatorio. Nel 1997 uscì il loro primo demo, Cemeterial Gardens, e tre anni dopo uscì il loro primo album, Winds of Creation, da molti considerato ancora il loro apice. Il successore, Nihility (2002) era un concentrato ancora maggiore di tecnica e brutalità. Questo stile continuò sul loro disco del 2004, The Negation.
Compresi tra i 18 (con Vitek) ed i 22 anni (con Vogg) loro sono probabilmente il gruppo più giovane ad aver raggiunto un grande successo nel genere. Martin e Vogg suonano anche in un altro gruppo polacco, i Lux Occulta, dediti al black metal.
Attualmente i Decapitated sono sotto contratto con la Earache Records, e all'inizio del 2006 hanno pubblicato il disco Organic Hallucinosis, che vide un'evoluzione nel loro stile. Il disco in questione era infatti meno marcatamente brutal, richiamando più all'industrial/death metal tipico di gruppi come Fear Factory e Meshuggah.
Nell'estate del 2005, Sauron, il cantante, lasciò la band. Venne rimpiazzato da Covan, già componente dei Atrophia Red Sun.
Il 29 ottobre 2007, mentre il gruppo stava viaggiando verso Gomel, Bielorussia, insieme ai Crionics, viene coinvolto in un incidente stradale a Novozybkov in Russia non lontano dal confine con la Bielorussia. Adrian Kowanek e Witold Kiełtyka rimangono gravemente feriti, nei giorni successivi il cantante mostrerà dei progressi, ma il giovane batterista morirà il 2 novembre all'età di 23 anni.
Dopo oltre due anni, il 20 novembre 2009, il chitarrista Waclaw Kieltyka annuncia il ritorno della band con un tour in Gran Bretagna e una formazione totalmente nuova: Kerim Lechner sostituirà Witold alla batteria, Rafał Piotrowski l'ancora convalescente Adrian Kowanek alla voce e Filip Hałucha sarà il nuovo bassista live.
Nel 2017 esce per Nuclear Blast il loro settimo album "Anticult".
Nel 2021 la label tedesca ristampa i primi due demo in un unico disco dal titolo "The First Damned"