Durante o rigoroso inverno suéco, em outubro de 92 ,  3 jovens suécos apaixonados por skate resolveram formar uma banda hardcore. Os 3 já tocavam em bandas punk ou hardcore, mas essas bandas cantavam em suéco.
Nikola, desde o início fazia as coisas que mais sabia: compor, cantar e tocar baixo. Mathias, naquela época começou na bateria e Erik já tocava guitarra. Nikola e Mathias tocavam juntos em uma banda chamada Seigmenn, enquanto Erik tocava em uma banda chamada Charles Hårfager.
Eles andavam de skate desde 87 e curtiam sons como Operation Ivy, Mc Rad, Descendents e Odd Man Out, que conheceram através de vídeos de skate e de snowboard.
A banda já estava formada mas ainda faltava uma coisa: o nome. Então optaram pelo nome de Millencolin.
Este nome vem de uma manobra de skate chamada melancholy (também conhecida como sad air), só que resolveram alterar um pouquinho para soar melhor como um nome para a banda.
No verão de 93 gravaram uma fita demo com 10 músicas chamada Melack (me + lack).
Ainda em 93 gravaram mais uma fita demo, também com 10 músicas, chamada Goofy.
Estas fitas chamaram a atenção do produtor Dan Swanö, que os chamou para o Unisound Studios no qual a banda continuou gravando discos até o For Monkeys.
A iniciante gravadora Burning Heart Records propôs-se então a lançar os futuros álbuns do Millencolin.
Quando perceberam que eram necessários 2 guitarristas para as apresentações ao vivo, Mathias abandonou as baquetas e foi para a guitarra (segundo Erik ele era melhor como guitarrista do que como baterista).
Para prencher a vaga na bateria, em outubro de 93 foi chamado Larzon, que tocava em uma banda chamada Kung Pung.
As bandas anteriores dos membros do Millencolin (Charles Hårfager, Seigmenn e Kung Pung) lançaram um 7" cada uma.
Tanto o Seigmenn quanto o Kung Punk terminaram ainda em 93.
Já o Charles Hårfager teve melhor sorte e assinou com a Kamel Records, que relançou seu 7".
Erik ainda gravou mais um single com o Charles Hårfager (chamado Korpen Faller) antes de abandonar a banda.
Nesta época, Erik pôs em circulação seu fanzine chamado Jagular Music & Skate Zine, mas lançou só uma edição.
Em setembro de 93 gravaram um single chamado Use your Nose, com 6 músicas.
Em maio de 94 gravaram o single Skauch, com 6 músicas, sendo que 4 eram covers.
Em agosto entraram em estúdio mais uma vez, agora para gravarem seu 1º LP, que se chamava Tiny Tunes. Só que a Warner Bros. entrou com um recurso na justiça contra a Burning Heart, já que a capa e o nome do álbum parodiavam o desenho animado da Warner, Tiny Toons.
Na 2ª prensagem, a capa acabou sendo mudada e o nome do disco passou a ser Same Old Tunes, já que possuia as mesmas músicas.
O álbum atingiu a 9ª posição nas paradas suécas e o disco acabou fazendo um grande sucesso, pelo menos para uma banda iniciante.
A música Da Strike chegou ao 4º lugar nas paradas da Suécia e o seu clipe passava em quase todas as estações de tv deste país.
Neste ano eles fizeram muitos shows, mais de 100 só na Suécia.
Em 95 tanto a Burning Heart quanto o Unisound Studios transferiram-se para Örebro, cidade natal da banda.
Em agosto de 95 entraram em estúdio para gravarem seu 2º LP, entitulado Life on a Plate.
O disco foi lançado em outubro de 95 e na época vendeu 25 mil cópias só na Europa.
Neste verão tocaram em 24 festivais, entre eles o de Kalvöja na Noruéga e o de Roskilde na Dinamarca.
A esta altura já haviam conquistado a Escandinávia, agora faltava conquistar o resto do mundo.
O primeiro passo para isso foi dado em setembro de 95, quando fizeram sua primeira turnê fora da Escandinávia. Fizeram shows primeiro na Alemanha, depois na Suíça, França e Inglaterra.
Em dezembro de 95 Brett Gurewitz (ex-guitarrista do Bad Religion e dono da gravadora Epitaph) entrou em contato com a banda demonstrando interesse em lançar Life on a Plate nos EUA. O álbum foi lançado nos EUA em março de 96.
Em 96 fizeram mais de 150 shows, no Japão, Austrália, Canadá e EUA, participaram de festivais de verão na Europa, além de uma turnê pelo sul europeu.
Em janeiro de 97, entraram em estúdio para gravar seu 3º álbum, chamado For Monkeys.
No final de março de 97 saiu o 1º single para este álbum, contendo 3 músicas (Lozin' Must, Vixen e Israelites).
No dia 21 de abril 97 o disco For Monkeys foi lançado.
O título surgiu da brincadeira de os integrantes da banda se chamarem de monkeys (macacos).
O título original era para ser Four Monkeys (4 Macacos) mas alguém sugeriu For Monkeys (Para Macacos) e eles aceitaram.
A turnê de divulgação do álbum For Monkeys teve início em maio de 97 e terminou em agosto de 98.
A turnê incluiu 3 viagens à Europa, 3 para os EUA e Canadá, e uma para o Japão, Austrália, Brasil e Argentina. Esta turnê chegou a quase 200 shows !
Depois da turnê lançaram um home-video chamado Millencolin & the Hi-8 Adventures.
Lançaram também uma coletânea chamada The Melancholy Collection. Nesta coletânea encontram-se os 2 primeiros singles, os B-sides e algumas músicas gravadas para outras coletâneas.
Em agosto de 99 foram aos estúdios West Beach, em Los Angeles, para gravarem seu 5º álbum.
No dia 21 de fevereiro de 2000 é lançado o álbum The Pennybridge Pioneers.
Este disco marca uma nova fase na carreira do Millencolin, pois agora  abandonaram o ska, presente em todos os discos anteriores. Este disco também é mais lento que os anteriores, mas mesmo assim é um excelente álbum, com músicas excelentes como No Cigar, Fox e Penguins and Polarbears.