Команда была образована гитаристом Вацлавом «Vogg» Келтыкой, его братом ударником Витольдом «Vitek» и вокалистом Войцехом «Sauron» Восовичем. Средний возраст участников составлял 14 лет на момент создания команды. Год спустя к ним пришел басист Марцин «Martin» Рыгель, которому было 13 лет. В июне 1997-го ребята записали своё первое демо «Cemeteral gardens».
В октябре 1998-го вышла вторая демка, «The Eye of Horus», включавшая помимо собственных четырех треков кавер «Slayer» — «Mandatory Suicide». На этот раз к творению команды более взрослые слушатели отнеслись с уважением, а концертная деятельность помогла Decapitated занять достойное место в польском андеграунде. Записывающие фирмы начали наперебой предлагать контракты. Музыканты остановили свой выбор на «Earache records», где также располагались их кумиры Vader.
Дебютный альбом, «Winds of Creation», вышел в апреле 2000-го, получив массу положительных отзывов. В поддержку диска Decapitated совершили турне по Англии в компании с Lock up. В 2001-м польские дэтстеры разъезжали по Европе, сопровождая Immolation.
Когда средний возраст участников команды приблизился к двадцати годам, Decapitated самостоятельно выпустили второй альбом, «Nihility», вышедший в феврале 2002 года. С этим диском, содержавшим кавер Napalm Death, группа окончательно забронировала себе место на польской сцене, наряду с Vader и Behemoth. Последующие гастроли коллектив провел с Incantation, Vehemence, Dead to fall в Северной Америке и с Vader, Krisiun, Prejudice в Европе.
Новая студийная работа Decapitated вышла в августе 2004-го. «The Negation» получил в прессе высокие оценки. В 2005 году Саурон покинул группу и его место занял Кован, ранее числившийся в Atrophia Red Sun.
7 февраля 2006 года вышел четвёртый альбом «Organic Hallucinosis». Он заметно отличается от предыдущих работ своей техникой и модерном, своего рода отход от старой школы.
2 ноября 2007 года трагически скончался ударник группы, Витольд Келтыка. Автобус музыкантов, ехавших на концерт в г. Гомель (Беларусь), столкнулся с лесовозом недалеко от Российско-Белорусской границы. Двое участников группы, ударник Vitek и вокалист Адриан «Covan» Кованек, попали в реанимацию. Мартина с ними на тот момент не было, он перебрался в Калифорнию. Они получили серьёзные травмы черепа. По неподтвержденным данным, виноват в аварии был водитель автобуса. Витольд скончался в российской больнице от полученных в результате аварии травм. Ему было всего 23 года.
7 января 2008 года в клубе «Стодола» (Stodoła) состоялся благотворительный концерт, инициатором которого был лидер Vader’а Peter. Прибыль с продажи билетов, маек и дисков была направлена на помощь семье Витольда и на лечение Covan’а. В концерте приняли такие знаменитости польской метал-сцены как Virgin Snatch, Frontside, Behemoth и Vader. Также гитара Peter’а из Vader была выставлена на аукционе, средства с её продажи также пошли на помощь семье Келтыка и лечение Covan’а.
Новый альбом под названием Carnival Is Forever, писался в "RG" студии в Гданьске, Польша. Они приступили к записи альбома 9 февраля 2011 года, и закончили его 31 марта.
1 ноября 2011 года группа была на борту самолёта, совершившего аварийную посадку, никто не пострадал.
Осенью 2014 года вышел шестой их альбом Blood Mantra
Нынешний состав группы:Вацлав Келтыка-гитара,Рафал Пиотровский-вокал,Павел Пасек-бас,Михаил Лысейко-барабаны.
12 сентября 2017 года в СМИ появилась информация, что участники группы обвиняются в групповом изнасиловании девушки, находившейся с ними в тур-автобусе. Происшествие случилось 31 августа 2017 в городе Спокан, штат Вашингтон, США.
5 января 2018 года все обвинения с участников группы были сняты.
