Im Oktober 1992 wurde in Örebro in Schweden von Erik, Nikola und Mathias die Band Millencolin gegründet.
Vorher spielten die Jungs in verschiedenen anderen Punkbands und sangen schwedische Texte.

Der Name Millencolin entstand aus dem Skatetrick Melancholy, den sie ein wenig veränderten, so dass er sich mehr wie ein Name anhörte. Sie nahmen 1993 ein Demotape mit zehn Liedern auf, das sie Goofy nannten. Als letzter trat der Drummer Frederik, der vorher in einer Band namens Kung Pung spielte, in die Band ein. Da sie aber schon einen Drummer hatten, und einen zweiten Gittarenspieler benötigten, wurde Mathias der bis dahin der Drummer war zum Gitarrist umfunktioniert.

Dann nahmen sie in den Unisound Studios ein Tape mit zehn Songs auf, welches sie Melack nannten. Jemand sendete das Tape zu dem Plattenlabel Burning Heart, welche die Band dann unter Vertrag nehmen wollte.

Anfang 1994 nahmen sie ihre erste richtige  Single-CD Use Your Nose auf, die aus sechs Tracks bestand. Im selben Jahr veröffentlichten sie ihr erstes Album namens Tiny Tunes, zu dem viele live Konzerte gespielt wurden, 100 davon alleine nur in Schweden.

1995 zogen das Label Burning Heart und die Unisound Studios um nach Örebro und im August 1995 nahm Millencolin ihr zweites Album auf, welches sie im Oktober 1995 mit dem Namen Life On A Plate veröffentlichten. Im Sommer 1995 spielten sie auf insgesamt 24 Festivals, Kalvöja in Norwegen, Roskilde in Dänemark und alle anderen 22 in Schweden. Im September 1995 spielten sie eine Tour erstmalig außerhalb von Skandinavien. Sie spielten eine Tour mit zehn Konzerten in Deutschland. Ein Paar Wochen später starteten sie eine andere Europa Tour und spielten unteranderem in der Schweiz, Frankreich, England und nochmals in Deutschland.

Die meisten Touren startete Millencolin 1996. In diesem Jahr spielten sie in Japan,   Australien, zweimal in den USA und Kanada und auf einigen Europäischen Festivals. Insgesamt spielten sie 1996 150 Konzerte.

Ein wenig später wurde Burning Heart von der Filmproduktions Firma Warner Bros. verklagt, weil sie mit dem Namen des Albums Tiny Tunes, aufgrund der gleichnamigen Comicfernsehserie, nicht einverstanden waren. Deshalb musste Millencolin das Cover und den Namen  ändern. Sie entschloßen sich nach langem überlegen die CD nun Same old Tunes zu nennen.

Die For Monkeys Tour startete im May 1997 und endete im August 1998. Die Tour enthielt drei Europareisen, eine Reise nach Australien und Japan, drei Besuche in den USA und Kanada und einen Besuch in Südamerika. Insgesamt spielte Millencolin auf der For Monkeys Tour fast 200 Konzerte.

1998  stellten sie aus älteren Songs einen Sampler mit dem Namen The Melancholy Collection zusammen.