At the time Bliss was at college in Birmingham, but after 'Rollo Goes Camping' became their first top 30 hit she didn't go back. She was already making a name as a DJ and her musical skills she's a classically trained pianist became invaluable to Rollo, who has plenty of ideas but can't play a thing.

Rollo wanted to start a label so together they made the first Cheeky release in Bliss's mum's bedroom, a DIY effort with Bliss singing that she now says was "beyond terrible". Since they had no idea how to distribute it, most of the copies simply sat around in boxes. More one-off dance singles followed, but the story probably would have stopped there had Mel Medalie of indie dance label Champion not offered them a deal. He would fund Cheeky, they could make the music they wanted, and the profits would be split 50/50. A string of one-off dance hits followed. Then in 1995 Rollo thought it might be fun to do a track with a rapper and arranged to meet Maxi Jazz, a pirate radio veteran who was working with several hip hop and jazz bands in London. "I was impressed because he was a dance producer but he wasn't expecting me to write 'throw your hands in the air'," recalls Maxi. "He wanted a rhyme about frustration, about somebody who feels so bad he can't even live in his own skin. So I wrote the lyrics and he was taken by them because I guess in general people would write about the situations that frustrate, whereas I was more concerned with the state of mind that causes frustration. When you've got no self-confidence to deal with anything."

Maxi was a recent convert to Nicherin Daishonin's Buddhism; Rollo had a philosophy degree. So they found plenty to talk about together. Shortly afterwards Rollo met Jamie Catto, a well-travelled hippy singer with a passion for world music and an aversion to washing. He decided it was time for Cheeky to make its first album.

Reverence was made in 17 days. "We'd just find things that inspired us and say, 'Let's do something like that!'" says Bliss. "A reggae bassline that I'd always liked, a tune that had taken Rollo's fancy because it was in waltz time, whatever."

Jamie wanted to record his vocals naked, but compromised by just taking his shirt off. Maxi's lyrics poured out, and Rollo took Bliss a pizzicato string sound which she quickly turned into a riff because they wanted to go out shopping. Rollo's sister Dido hung out at the studio after work, making tea and begging to be allowed to join in. Bliss argued Dido's case, and eventually he let her put down a vocal or two.

In July 1995 'Salva Mea' became the first single, spending one week at the bottom of the UK top 30 before disappearing. In December 'Insomnia', the song they made from that soon to be widely copied pizzicato riff, reached number 27 in the UK singles chart. In between, the album sold just 4000 copies worldwide. In an attempt to promote it a little more, Faithless played their first live gig at Camden's Jazz Café in March 1996, packing out the 400-capacity venue with family and friends. The group didn't have enough songs for a full live show so everyone involved Maxi, Jamie, singer Pauline Taylor and Dido threw in a couple of their own.

Word got out that Faithless could play live, invitations began coming in to play in Austria, Switzerland and Germany, where 'Insomnia' had been hovering at the bottom of the top 100 for months. Only a few months after their live debut, the group played to 5000 people in a Mercedes factory in Baden Baden. It's a night all three of the group's core members remember vividly: the night they knew Faithless was becoming something more than a bunch of mates having fun.

"I stood outside looking at all these people who had bought tickets to see Faithless, while Mel at the Cheeky office in London read me the chart positions around Europe," recalls Rollo. "It was our little company! That was the first time I'd ever had that experience. Number 2, 1, 3, 4 the list went on and on."

In the bus afterwards, they listened to a recording of the show. As Maxi recalls: "We were all looking at each other with our mouths open saying, 'God, we sound like a proper band, don't we? No wonder they're going mad it sounds really good!' From that second, we knew we had something."

By September, both 'Insomnia' and 'Salva Mea' were competing with the Spice Girls' debut single for the number one slot around Europe. Maxi and Bliss now took Faithless on tour seriously, honing their live act, learning as they went along. Rollo stayed in the studio in London and stopped doing interviews as part of the band, choosing to become "an enigma". They have never had a manager, and in theory he also takes care of the business side, but he cheerfully admits that he often forgets. "We muddle along," he shrugs. "It's very DIY. We have meetings, talk on the phone, make decisions together. That's something we can be proud of." By the time they started work on their second album Sunday 8pm, Faithless had been on the road too long. The band's guitarist Dave Randall turned up one day in a 'God is a DJ' T-shirt that inspired the album's big hit single, and Boy George guested on the achingly beautiful torch song 'Why Go?'. But on the whole, it was an inventive but dark album. "We were all pretty morose," explains Bliss. "The constant touring had put a strain on relationships, and almost everyone in the band was involved in a break-up during this period."

Still their reputation as one of Britain's best live acts continued to grow, and by the end of the 1990s they'd played all the big summer festivals in the UK and across Europe, even causing a minor earthquake at PinkPop in the Netherlands by urging the 60,000-strong crowd to all jump at once. In the meantime Rollo let go of his dream of running a mini-Motown at Cheeky, eventually negotiating a deal to sell the label to BMG while retaining creative control. So Outrospective became the first Faithless album on a major label, and with the pressure on once more to produce a hit single, they mixed 'We Come 1' 30 times before finally feeling it made the grade. It has since become the track many top sound designers use when building and testing sound systems in nightclubs. "I was so glad when I heard that," says Rollo, "because we really worked to get that particular piece of music right."

In the summer of 2002 they headlined all the big European festivals: Roskilde in Denmark, Norwegian Wood, Hultsfred in Sweden, Rock Werchter and PinkPop in the Netherlands. And then there was Glastonbury, where Faithless headlined on the main stage before Coldplay. It was a clear, warm night, and the atmosphere was magical. Faithless took the stage like they owned it, and everyone present knew they'd witnessed something extraordinary. "It was one of those awe-inspiring times when you feel, 'God, this is what all the bollocks has been for,'" says Bliss. "That was particularly special."

By the time they came to make their 2004 album No Roots the world had changed dramatically, and Faithless felt they had something to say about it. They didn't even try to produce an obvious hit. "Leading with the single 'Mass Destruction' was a real break with tradition," explains Bliss. "But it was important for us to show the other side of Faithless the content of what Maxi says." Leeds singer/rapper LSK was their main collaborator. "His outlook on life is much the same as mine," says Maxi. "We're both old-school B-boys, into old-school reggae and hip hop as a culture rather than just rap music. I find him totally inspiring. And because of him, this last album has been lyrically probably the most focussed we've ever done. All of the songs are pointing in the same direction."

The grainy video showed children playing war games, kneeling in what was to prove an eerie premonition of the beheadings in Iraq. The video went into MTV's top ten and 'Mass Destruction' received heavy rotation on influential US radio stations like K Rock. One US Senator even appropriated the lyrics for a political speech. In the UK, meanwhile, the album went straight to number one, confirming the band's position as the people's favourite.

Next up is a greatest hits album, Forever Faithless, supported by yet more live shows. They're proud to have waited until they actually have enough material to justify such a collection they even ended up having to cut the album down. So ten years on, what's important to know about Faithless?

It isn't a group formed from friends who met at college or a club, says Maxi. "We're completely different musically, socially, in every way. When you extend that past the three of us to the entire band, it becomes even more diverse. Then when you include also the regular road crew who've been with us for the last ten years, that makes about 18 of us who are about as different as 18 people can possibly be.

"It's not a question of putting those differences aside in order to work together, it's about us all bringing our differences to the table and by doing so creating something that is greater than the sum of its parts. Love and unity. Call me an old hippie, but to me that's what we do, what we achieve as a group. That's what it's all about music as an expression of humanity."

"When we do a record, there isn't anything that sounds like it at the time," Rollo points out. "Things come to sound like it, but for better or for worse we stand in our own corner musically. For me, it's still so exciting when Maxi comes up with a great lyric. When he comes down the studio, we don't hear what he's done in advance. So we run the track round and round and he's usually tweaking it for a couple of hours. Then he finally goes, 'Right, it's ready.' And when it's like 'Mass Destruction', 'Bring My Family Back' or 'Reverence', you just think 'Wow!' When I make music now, I genuinely do it because I want to be in the studio that moment when you get the goose-bumps. I want to move people, and I want to be moved. And Maxi still can excite that in me." "I think the live arena has changed people's perceptions of us," says Sister Bliss. "We've been up there with the likes of REM, Robbie Williams, Bob Dylan all these different kinds of music. I've always been a real crusader for house music and what it means, that feeling inside, when something has got the right sounds and the funk and it makes you feel stuff. I want our own music to have that feeling. It's nice to be able to go out and turn heads, to hear people say, 'I don't like dance music but I quite like Faithless.'"

So there will definitely be a new Faithless album? "I've just done 30 new fragments of backing tracks," she says. "Forever Faithless might not be so far from the truth."