Оригинальный состав, состоящий из Сарцевика (вокал и бас), Олсона (гитара), и Фарма (ударные), выпустил свою первую демозапись, Goofy, в начале 1993 года. Вскоре к группе присоединился Дарзон в качестве ударника, что позволило Фарму стать вторым гитаристом. Летом 1993 года они записали второе демо, Melack. Группа отправила запись в Burning Heart Records, новый рекорд лейбл, основанный годом раньше. Они предложили Millencolin записать сингл, в результате чего в ноябре 1993 года он был выпущен под названием Use Your Nose. Успех сингла подтолкнул Burning Heart к предложению записать полноценный альбом. В июле 1994 года группа выпустила Skauch, изначально планировавшийся как сингл к новому альбому. Однако, группа решила записать четыре кавер-версиии включила их в альбом. Они выпустили первый крупный релиз, Tiny Tunes, в 1994 году. Запись и сведение альбома заняли всего две недели.
Дебютный альбом сразу сделал группу одной из центральных фигур на шведской панк-сцене. Песня «Da Strike» поднимается на 9 место в национальном Шведском хит-параде, видео на нее крутят по нескольким шведским телеканалам и в первый же месяц распродается около 20 000 экземпляров альбома. Парни активно катаются по стране с концертами, количество которых к концу года переваливает за сотню.
Лето следующего года также стало очень насыщенным для группы. Они засветились практически на всех фестах альтернативной музыки, которые проводились в то время, а затем впервые отправились за пределы Скандинавии в тур с Pennywise и No Fun At All по Японии и Германии. В августе 95-го группа приступает к записи своей второй пластинки «Life On A Plate» (1995), релиз которой состоялся в октябре. Альбом продолжил успех предыдущего диска группы, попав на 4-ое место в национальном чарте и став в Швеции настоящим хитом. Успеху во многом способствует активный пиар в СМИ — «Story Of My Life» и «Move Your Car» вовсю крутят по радио, а видео на эти песни не сходят с экранов TV. Вскоре группа отправляется в свой второй Европейский тур, на этот раз по Швейцарии, Англии, Франции и Германии.
В конце 95-го Бретт Гуревич из Epitaph, заинтересовавшись перспективной шведской командой, подписывает контракт с парнями на переиздание «Life On A Plate» на своем лейбле в Штатах. С выходом этого диска, который состоялся в марте 96-го, группа становится известной по другую сторону океана и колесит по всему миру с концертами. Япония, Австралия, два концертный тура по Штатам и Канаде, несколько европейских летних фестивалей и южноевропейский тур — в течение 1996 года группа дает более 150 концертов.
В начале 97-го группа отправляется в свою студию Unisound для записи третьего альбома «For Monkeys» (1997) (то есть «для обезьянок», как ласково называют своих слушателей музыканты). Диск выходит 21 апреля и показывает группу с новой стороны. Его общее время звучания около получаса, ска уже заметно меньше, а сами песни стали более медленными и запоминающимися. После выхода альбома турне в его поддержку, которое продлилось более года — с мая 97-го по август 98-го. Вернувшись из турне в полностью разобранном состоянии (шутка ли — год в дороге) парни берут небольшой отпуск до начала 99-го.
В это время выходит их первая видеокассета под названием «Millencolin & The Hi-8 Adventures» — 76 минут видео под редакцией Эрика. Тут есть все — от живых выступлений группы до катания ее участников на досках. Параллельно издается альбом «The Melancholy Collection» (1999), включивший в себя вещи с первых двух EP, B-сайды других синглов и песни записанные для различных сборников — материал с 93-го по 98-ой год, в общей сложности 22 трэка.
В начале 99-го Mr.Brett подкатывает к группе с заманчивым предложением о записи нового альбома. Причем нигде нибудь, а в знаменитой Westbeach Studios в Голливуде. И с ним самим в роли продюсера. Предложение из тех, от которых не отказываются. Так появился четвертый альбом «Pennybridge Pioneers» (2000) (в переводе на английский Ore=Penny, а Bro=Bridge). Записан он был летом 99-го в течение 6-ти недель, а выпущен в феврале 2000-го. Бретт основательно приложил руку к записи диска, альбом сильно отличается от звучания ранних работ группы и не в лучшую сторону — музыка заметно потеряла в оригинальности, эдакая типичная пластинка команды из Epitaph-тусовки, тем не менее энергично и профессионально сыгранная. Последовавший концертный тур включил в себя выступления в Европе, Австралии и Новой Зеландии, а также на Warped Tour 2000. В перерывах между концертами группа пару раз смоталась в Лос-Анжелес, где было отснято 2 видео на песни «Penguins & Polarbears» и «Fox».
В конце 2000-го парни приступают к записи нового материала. Альбом решено записывать на родине в Швеции. По рекомендации друзей из группы Samiam в качестве продюсера приглашен Lou Giordano ранее работавший с этой командой. Кстати, энтузиазм нового продюсера был подкреплен значительной порцией адреналина — его самолет из Нью-Йорка в Стокгольм вылетел 11 сентября 2001-го за пару часов до памятных всем событий в США. Новый альбом «Home From Home» (2002) был записан в Стокгольме в студии Little Big Room, вышел в марте 2002-го и музыкально стал логическим продолжением своего предшественника.
Вернувшись из последовавшего за релизом концертного тура, группа в октябре 2002-го празднует свое 10-летие. В Оребро в клубе Club 700 был организован праздничный концерт, который одновременно послужил открытием ежегодному скейт-фесту под названием Millencolin Open. В качестве почетного гостя был приглашен и крестный отец группы Бретт Гуревич, вышедший на сцену третьим гитаристом во время исполнения песен «Fox» и «American Jesus».