After looking back at their most successful career stretch last year via the The Melancholy Connection, an album of far from B-sides that revisited a whole bunch of passed-over gems that have been recorded since their landmark 2000 release, Pennybridge Pioneers, Millencolin are once again focused on the future. No surprise then that their first stop is Australia, the quartet signing up as one of the headline acts at Warped Tour 2014.

“I think it's some kind of culture thing,” explains frontman Nikola Sarcevic, discussing the mutual affection that Millencolin and Australia have shared for two decades. “We come from some kind of skateboard/snowboard culture that goes pretty much hand in hand with the Californian and Australian lifestyle. That's how we started out playing music was listening to music that was on all the skateboard videos in the late-'80s and '90s, so for us I think we're quite close in culture.”

Millencolin first appeared on our radar with their 1995 second album, Life On A Plate. Although they put a debut out before that in their native Sweden, this was the first record that saw a worldwide release, their musical mixture of punk speed, rock muscle and whimsical, relatable lyrics generating the band a global audience following their signing to iconic Cali imprint Epitaph.

“I was surprised [that people were listening],” Sarcevic remarks, “especially famous names within the genre like Fat Mike [NOFX] and Mr Brett [Gurewitz – Bad Religion] y'know, people like that were actually liking our music, I was a bit sceptical, like, 'No, are they really?', because we thought they were on a completely different level, gods or whatever. But step by step our confidence and awareness of actually having people liking our stuff has grown, and now it's something natural for us. We don't take it for granted but now we're used to it.”

The Örebro foursome's popularity in Oz peaked between 2000 and 2002. During that time Millencolin received solid national airplay via triple j, played the main stages of both Livid and Big Day Out, and their two albums released within that period – Pennybridge Pioneers and 2002's Home From Home – both went on to be certified gold. Since then things have slowed down considerably on the recording front, with only two more studio full-lengths, but now after taking time out for family and solo endeavours, it feels right that the next thing to come will be an eighth record.

“We're at an interesting point where we have good ideas so let's just see what they will turn into,” Sarcevic says, not giving too much away. “There's a plan for something in the future. We've taken a good time now off – it was a long time since the last full-length studio album – but we needed that time, and as you can see maybe we need more and more a longer time period between the albums. In a way it can be a bit stressful because you realise, 'Shit, it's been a long time', but you have to have patience and wait because you need to live your life away from the band, to get decent input into yourself to be able to come up with actual output of songs. We'll see. I'm looking at the future in a positive way with the band.”

When The Music gets on Skype with the bassist and vocalist, Warped Tour has just announced the skateboard and BMX names that will also be on the road for the tour, legends like Steve Caballero, Renton Millar and Neal Hendrix. Knowing the Millencolin guys are pretty handy on the double-kick deck – they're named after a skate trick after all – this info is passed on to Sarcevic.

“Is Cab doing the tour?” Sarcevic questions, jumping into the conversation like an excited kid when he hears Caballero's name mentioned. When the response is affirmative, he's audibly stoked. But as far as joining the pros on the bowl, the frontman is only a maybe; the board he's more eager to play is covered in black and white squares.

“Me and Cab will play chess,” Sarcevic admits. “That's what we usually do when we meet. On the Warped Tour we are playing chess every night, both in '97 and 2000, like every day, every night.” And who had the upper hand Nikola? “Well, I actually did,” he says with a humble chuckle. “But we were very even so it was really good games, but I think I won more games, but maybe this year – it's been a long time since we've played – he might have the upper hand, maybe he's a lot better than me now. So another great reason why it's going to be good to go [to Australia] – ahh! I didn't know this; I'm happy to hear.”