В январе 2006 года, через год после того как музыканты Nasum объявили о прекращении творческой деятельности группы, ударник Anders Jakobson приступил к поискам музыкантов для нового проекта. Вскоре гитарист Anders Bertilsson (Ruin) предложил свои услуги и был принят в команду. Примерно в то же время Oskar Pålsson, басист Relentless, искал сессионного ударника для записи демо. Он обратился к Anders Jakobson, который в свою очередь рассказал ему о своих поисках. Парни решили объединить две идеи в одну.

В феврале того же года состоялась первая репетиция, было записано несколько песен. Музыканты приняли решение о включении в состав группы второго гитариста. В блоге Anders'а Jakobson'а было объявлено о начале поисков четвертого члена группы. В марте 2006 года второй гитарист был найден - им стал André Alvinzi (Carnal Grief). Группа вновь приступили к репетициям.

В начале апреля 2006 года музыканты огласили название группы - Coldworker. После попыток Anders'а Bertilsson'а петь музыканты пришли к выводу, что им необходим участник группы, который полностью сосредоточился бы на вокальных партиях. В середине того же месяца в группу был принят вокалист по имени Joel Fornbrant (ex-Phobos). Впятером парни продолжили писать песни и активно репетировать.

В июне того же года состоялся первый концерт Coldworker совместно с Gadget и Radioskugga. Вскоре после выступления Coldworker приступили к записи первого альбома. Пластинка получила название "The Contaminated Void". Запись продолжалась в течение трех недель. Микширование выполнил Dan Swanö, а мастеринг осуществлен Peter In De Betou. Скопировано с Dark-World.ru. Далее был заключен контракт с Relapse Records.

В преддверии выхода дебютного альбома Coldworker в августе-сентябре 2006 года отыграли два концерта. 6 ноября 2006 года состоялся релиз "The Contaminated Void" по всему миру на виниле и в Европе на дисках. Сразу после релиза парни отыграли десять концертов по всей Швеции и Дании в рамках тура Close-up Made Us Do It вместе с Arch Enemy и Path of No Return.

В январе 2007 года André Alvinzi был заменен на Daniel'а Schröder'а (также из Ruin). Месяцем позднее группа приняла участие в финском фестивале Finnish Metal Expo, который прошел в Хельсинки. В июне этого же года Coldworker отправились в двухнедельный тур по Европе вместе с Misery Index и Dew-Scented, в ходе которого посетили такие фестивали, как Fury Fest и Summer Blast. С момента завершения тура и до конца года группа работала над материалом для второго полноформатного альбома.

В декабре 2007 - январе 2008 проходила запись второго полноформатника под названием "Rotting Paradise". Запись происходила в четырех разных местах: ударные были записаны в студии Soundlab; гитары записали дома у Johan'а Berglund'а из This Haven; бас-гитару - дома у Anders'а Jakobson'а; а вокал - на репетиционной базе Coldworker. Микшированием и мастерингом вновь занимался Dan Swanö. Всего было записано пятнадцать песен. Из них двенадцать оказались на альбоме, тринадцатая - кавер-версия песни Sepultura "Necromancer" - попала на японскую версию альбома, а оставшиеся две песни музыканты приберегли на будущее.

"Rotting Paradise" был выпущен 13 мая 2008 года на виниле и дисках. После нескольких концертов в Швеции и других странах в поддержку альбома Coldworker приступили к записи кавер-версий песен Nasum "Den Mörka Tiden" и Repulsion "Crematorium" для трибьют-альбомов этих групп.

В январе 2009 года Coldworker вместе с The Black Dahlia Murder отыграли несколько концертов, последний из которых состоялся в родном городе участников группы - Эребру. В июле месяце FDA Rekotz выпустили "Tribute to Repulsion" на виниле. В августе того же года на Power It Up Records состоялся релиз семидюймового сплита с Deathbound. Для этого издания Coldworker использовали оставшиеся две песни со времен "Rotting Paradise".

В октябре того же года парни отыграли небольшой тур по Швеции совместно с Remasculate. В ноябре состоялся релиз "Tribute to Nasum" на виниле и дисках посредством Power It Up Records. Месяцем позже "Tribute to Repulsion" вышел на компакт-дисках .

Большую часть 2010 года Coldworker писали новые песни и репетировали. В мае 2010 в Эребру прошел благотворительный фестиваль, в котором группа приняла участие. Вскоре началась запись третьего альбома, которая вновь проходила в студии Soundlab. Запись ударных была завершена за несколько дней до Рождества. В январе - феврале 2011 года были записаны остальные инструменты, но уже в студии Ülgnor и с помощью Johan'а Berglund'а. Вокал снова был записан на репетиционной базе группы. Альбом получил название "The Doomsayer's Call".

Весной 2011 года Relapse Records отказались выпускать новый альбом и разорвали контракт с группой. Вскоре французский лейбл Listenable Records проявил интерес к Coldworker, и начались переговоры, а в августе был подписан контракт.

Оформление обложки для третьего альбома было поручено известному художнику-оформителю из Швеции Pär Olofsson. Группа хотела, чтобы обложка была другого типа в сравнении с обложками двух предыдущих альбомов, однако, от концепции фигуры посередине рисунка отказываться не хотели. Они хотели что-то ретро-футористическое, вдохновленное фильмом 1927 года "Метрополис". Альбом вышел 13 февраля 2012 года.

В субботу, 6 июля 2013 года, на сайте Lambgoat.com появилось сообщение о распаде группы с официальным обращением самих музыкантов: