Nell'ottobre del 1992 tre skaters svedesi, di Orebro, che ascoltano band come Operation Ivy e Descendents già dal 1987 si incontrano. Si chiamano Nikola "Kola" Sarcevic, Mathias Färm (i due suonano in un gruppo chiamato Seigmenn, rispettivamente alla voce e basso e alla batteria) e Erik Ohlsson (che suona nei Charles Harfager): i tre decidono così di formare una band, i Millencolin, prendendo il nome da un'acrobazia con lo skate-board chiamata melancholy. Nel '93 il gruppo produce il primo demo-tape, "Goofy", e dopo il loro primo show, ai tre si unisce Fredrik Larzon (che lascia i Kung Punk) che sostituisce Mathias alla batteria, il quale passa alla seconda chitarra. La stessa estate esce il secondo demo, "Melack", le cui canzoni vengono inserite anche in alcune compilation. Dopo poche settimane vengono notati da Dan Swano che aveva appena fondato la casa discografica Burning Heart Records per la quale, dopo poco tempo, registrano all'Unisound Studio il primo singolo "Use Your Nose", che esce nel settembre dello stesso anno, seguito nel maggio '94 da "Skauch". Nell'agosto dello stesso anno registrano il primo album, "Tiny Tunes", il cui nome viene presto cambiato in "Same Old Tunes" a causa di problemi legali con la Warner Bros. Il disco esce nel settembre dello stesso anno, vendendo circa 20000 copie nel primo mese, ed i concerti si intensificano, soprattutto in Svezia, mentre il singolo "Da Strike" arriva al nono posto delle classifiche del loro paese. La stessa estate partono in tour con i No Fun At All, con i quali suonano anche in Giappone, e nel 1995 registrano "Life On A Plate", che esce in ottobre e arriva fino al quarto posto delle classifiche svedesi. Il singolo "The Story Of My Life" viene passato costantemente dalle radio nazionali, mentre il suo video viene passato frequentemente su un canale televisivo svedese. Iniziano così a partecipare a parecchi festivals svedesi e norvegesi e arrivano a suonare in Germania, Svizzera, Francia ed Inghilterra, venendo notati dal proprietario della Epitaph, Brett Gurewitz (ex chitarrista dei Bad Religion), che li mette sotto contratto per il mercato americano e ristampa "Life On A Plate" per il mercato americano, dove esce nel marzo '96. Nel gennaio del '97 la band entra all'Unisound per registrare un nuovo full-length, "For Monkeys" (nome preso dalla consuetudine dei membri della band di chiamarsi tra loro monkey - scimmia), che esce in aprile, edito dalla Epitaph per l'America e dalla Burning Heart per il resto del mondo. Poco dopo Mathias acquista da Swano l'Unisound Studio, ribattezzandolo "Sound Lab Studio". Un mese dopo l'uscita del terzo album inizia il For Monkeys tour, che li vede suonare, fino all'agosto '98, 200 show in Europa, Australia, Giappone, USA, Canada e Sud America. Sempre nel '98 viene ristampato il primo cd della band, "Same Old Tunes", dalla Epitaph, per il mercato americano. A inizio '99 viene rilasciato dalla Burning Heart "Melancholy Collection", una raccolta di cover, brani inclusi nei primi due demo, b-sides e pezzi inseriti solo in delle compilations, mentre nell'estate dello stesso anno la band partecipa al Vans Warped Tour, suonando con band, tra le altre, come Pennywise e Lagwagon. In seguito si recano in California, al West Beach Recorders di Hollywood (studio di proprietà di Gurewitz e Donnell Cameron), negli Stati Uniti, per registrare "Pennybridge Pioneers", che viene rilasciato nel febbraio del 2000 (dalla Epitaph in America e dalla Burning Heart nel resto del mondo). Nel giugno del 2001 la Golf Records rilascia uno split con i Midtown (che contiene un inedito), mentre da settembre a novembre il gruppo registra al Little Big Room Studios di Haninge, in Svezia, un nuovo full-length (che contiene anche l'inedito dello split), "Home From Home", uscito sempre in collaborazione da Epitaph e Burning Heart.