Vier Jungs aus Schweden begannen 1987 zu skaten und wurden durch Skatervideos auf Punkrock aufmerksam. Man entschloss sich im Oktober '92 Millencolin zu gründen. Davor spielte Erik Gitarre bei “Charles Harfager”, Nikola und Mathias waren in der Band „Seigmenn“. Nachdem die drei Anfangs 1993 ein Demotape aufgenommen hatten und ihr erstes Konzert gegeben hatten, stiess Larzon als zweiter Gitarrist dazu. Er hatte zuvor bei „Kung Pung“ gespielt. Im Sommer 1993 nam Millencolin ein neues Demotape, in den „Unisound Studios“ auf, mit dem Namen „Melack“. Dieses landete bei „Burning Heart Records“, welches bisher erst zwei Single-CD’s releaste.“Burning Heart Records“ wollte von Millencolin ebenfalls eine Single rausbringen, was im November 1993 mit „Use your nose“ geschah. Die zweite Millencolin-Single wurde fünf Monate später wieder auf „Unisound“ veröffentlicht. Es folgte das erste Full-length-Album „Tiny Tunes“, welches später wegen einer Klage von Warner Bros. in „The same old tunes“ umgetauft werden musste. Der Song „Da Strike“ wurde ein Hit in Schweden und man spielte 1994 über 100 Konzerte in der Heimat. 

Das zweite Album „Life on a plate“ schaffte es bis auf Platz vier der Schwedischen Charts. Im September 1995 tourte man zum ersten Mal ausserhalb Skandinaviens, in Deutschland mit Pennywise. Darauf folgte eine zweite Tour durch Frankreich, England, die Schweiz und Deutschland. Ende 1995 releaste „Epitaph“ die „Life on a plate“-CD und man gab Konzerte in den Staaten, Kanada, Japan, Austalien und Europa – der definitive Durchbruch. Das dritte Album „Four Monkeys“ erschien 1997, worauf man wieder auf Tour ging. Nach 200 Shows auf fünf Kontinenten war man ausgebrannt. Nach einer Pause arbeitete man weiter und brachte das Video „Millencolin & the Hi-8 Adventures“ raus. Es folgte die Doppel-CD “The Melancholy Collection” mit Singles und B-Sides. 1999 folgte „Pennybridge Pioneers“, welches 1999 in LA in den Epitaph-Studios aufgenommen wurde. 2002 erschien "Home from home", 2005 "Kingwood", 2008 "Machine 15".

Der Bandname "Millencolin" ist abgeleitet vom Skatetrick "melancholy" (auch als "sad air" bekannt). Erik Olson (Gitarre), Nikola Sarcevic (Gesang/Bass), Mathias Färm (Gitarre) und Fredrik Larzon (Drums) waren stets darauf bedacht, ihre Integrität zu bewahren.