The original lineup, consisting of Sarcevic (vocals & bass), Ohlsson (guitar), and Färm (drums), released their first demo tape, Goofy, in early 1993. Soon afterwards, Larzon joined the band to play drums, allowing Färm to perform as the second guitarist. In the summer of 1993, they recorded a second demo tape, Melack. The band sent the tape to Burning Heart Records, a new record label formed earlier that year. They signed Millencolin to do a CD single, which culminated in the release of Use Your Nose in November 1993. Success of the single prompted Burning Heart to sign the band to release a full album. In July 1994, the band released Skauch, initially planned to be a single for their new album. However, the band decided to record four cover songs as well and released it as an EP instead. They put out their first major release, Tiny Tunes, in 1994. The recording and mixing of the album took two weeks. Legal trouble with Warner Brothers over the title and cover artwork of the album led the band to re-release it in 1996 under the name Same Old Tunes.
Millencolin continued to tour and in 1995 brought out their second full length album Life on a Plate. This coincided with Millencolin beginning to tour outside of Scandinavia. At the end of 1995, the US record company Epitaph Records wanted to release Life on a Plate in the US, and the band agreed. They then toured further afield, touring Japan, Australia, Brazil and Canada, and played as part of the 1997 Warped Tour.
Further albums For Monkeys and compilation The Melancholy Collection followed, but the band's popularity really increased in 2000 with the release of Pennybridge Pioneers, an album with more of a rock influence than the band's previous skate punk sound. The recording took six weeks and they started their first major worldwide tour. Millencolin played in Wellington, New Zealand, followed by an Australian tour. This led to an early release of the album in Australia and New Zealand. Millencolin wrote the following album on tour and brought out Home from Home in 2002. While it was not as well received as the previous effort, songs like "Happiness for Dogs" and "Afghan" showed a stronger and rockier sound which would greatly influence their next album Kingwood. In 2003 the band won the award for Best Swedish Rock.
Kingwood, released in March 2005, marked the band's return to a faster and more traditional skate punk -ish sound, collaborating it with their recently founded rock sound, and completed a world tour in follow up of the album. The album debuted at #2 in the Swedish chart.
In mid 2007, lead guitarist Erik Ohlsson announced plans for a new full-length album, a follow up to their DVD Hi-8 Adventures and a new website, amongst other things.
On October 22, 2007 the band entered the studio to start writing and recording songs for their seventh album Machine 15 that was released on April 7, 2008. The album showed a departure from their roots in skate punk shifting more torwards alternative rock. This change in sound earned them a lot of positive reviews but dissapointed some of their first day fans. A video for their first single "Detox" has also been released.
The band has hosted a skateboard contest at their own skatepark in Örebro, Sweden named the Millencolin Open. They say they started this annual contest because skateboarding is what brought them together and now they have the chance to make something good of their town and of skateboarding.
They wrote and released a single dedicated to their hometown football club Örebro SK titled Örebro in 2009. It was played in the stadium for the first time on May 11, 2009 in the home game vs Hammarby IF.
In 2010, they toured in Canada and South America, where they played Pennybridge Pioneers from start to finish. It was also announced they would be playing the 2011 Soundwave Festival in Australia.
- Nikola Šarčević – Vocals, Bass
- Mathias Färm – Guitar, Vocals
- Erik Ohlsson – Guitar, Vocals
- Fredrik Larzon – Drums
- 1994 - Tiny Tunes (Burning Heart/Epitaph; re-released as "Same Old Tunes" in 1998)
- 1995 - Life On A Plate (Burning Heart/Epitaph)
- 1997 - For Monkeys (Burning Heart/Epitaph)
- 2000 - Pennybridge Pioneers (Epitaph)
- 2002 - Home From Home (Epitaph)
- 2005 - Kingwood (Burning Heart/Epitaph)
- 2008 - Machine 15 (Burning Heart/Epitaph)
- 1999 - The Melancholy Collection (Burning Heart/Epitaph)
- 1999 - Millencolin And The Hi-8 Adventures (Burning Heart/Epitaph/Shock)
- 1993 - Goofy (Independent)
- 1993 - Melack (Independent)
- 1993 - Use Your Nose (Burning Heart)
- 1994 - Skauch (Burning Heart)
- 2001 - No Cigar (Burning Heart)
- 1994 - Da Strike (Burning Heart; from Tiny Tunes)
- 1995 - The Story Of My Life (Burning Heart; from Life On A Plate)
- 1996 - Move Your Car (Burning Heart; from Life On A Plate)
- 1997 - Lozin' Must (Burning Heart; from For Monkeys)
- 1997 - Twenty Two (Burning Heart; from For Monkeys)
- 2000 - Penguins & Polarbears (Burning Heart; from Pennybridge Pioneers)
- 2000 - Fox (Burning Heart; from Pennybridge Pioneers)
- 2002 - Kemp (Burning Heart; from Home From Home)
- 2002 - Man Or Mouse (Burning Heart; from Home From Home)
- 2003 - Battery Check (Burning Heart; from Home From Home)
- 2003 - E20 Norr (Burning Heart)
- 2005 - Ray (Burning Heart; from Kingwood)
- 2005 - Shut You Out (Burning Heart; from Kingwood)
- 2008 - Detox (Burning Heart; from Machine 15)
- 2008 - Broken World (Burning Heart; from Machine 15)
- 2001 - Millencolin/Midtown (Golf Records)
- 1993 - Tjöplusta (Brööl; song: "Yellow Dog" & "A Bit Of Muslin")
- 1994 - Really Fast Volume 9 (Really Fast; song: "Nosepicker")
- 1994 - Epitone (Brööl; songs: "Melancholy Protection" & "A Bit Of Muslin")
- 1994 - G.-Rock Around The Clock (G-Spot; song: Da Strike)
- 1995 - Pogo Tribe Detector (Ox Fanzine; song: Killer Crush)
- 1995 - Cheap Shots (Burning Heart; songs: "Shake Me", "Mr. Clean" & "Every Breath You Take")
- 1995 - Built To Rip (Burning Heart; song: "Killer Crush")
- 1995 - Popkomm '95 (Semaphore; song: "Take It Or Leave It")
- 1996 - Punk-O-Rama Volume 2 (Epitaph; song: "Bullion")
- 1996 - Cheap Shots Volume II (Burning Heart; songs: "Bullion" & "Killer Crush")
- 1996 - Kittenish 4 (Ultra Magazine; song: "Olympic")
- 1996 - Board To Hell (Viceroy; song: "Dr. Jackall & Mr. Hide")
- 1997 - Wheels On Fire (EVA; song: "Lozin' Must")
- 1997 - Audio-CD 10/97 (Audio Magazine; song: "Twenty Two")
- 1997 - Stronger Than Ever (Burning Heart; song: "Twenty Two")
- 1997 - Probably The Best Bands In The World… (Motor; song: "The Story Of My Life")
- 1997 - Cheap Shots Volume III (Burning Heart; songs: "Twenty Two")
- 1997 - Cinema Beer Nuts (Hopeless; song: "Lozin' Must")
- 1997 - Day Tripper (A&M; song: "Airhead")
- 1997 - 200-Proof-Punk (Destiny; song: "Fazil's Friend")
- 1997 - Snow Job (Poko; song: "Twenty Two")
- 1998 - Ska Sucks (Liberation; song: "Da Strike")
- 1998 - Punk-O-Rama Volume 3 (Epitaph; song: "Lozin' Must")
- 1998 - Punk Chartbusters Volume 3 (Wolverine; song: "Every Breath You Take")
- 1998 - Vans Off The Wall (Vans; song: "Random I Am")
- 1998 - Punk-O-Rama Volume 4 (Epitaph; song: "Mr. Clean")
- 1999 - Millencolin And The Hi-8 Adventures