My, my, my: Say hello to Delilah, the mouthy saviour of British pop

Few moan quite as mellifluously as Paloma Stoecker. Blustering into a record-company meeting-room, the singer-songwriter otherwise known as Delilah cheerfully curses the road-blocking rubbish truck that has made her 20 minutes late for our interview – the unwieldy vehicle being just the latest obstacle in a month that has turned into a "comedy of errors". First, she acquired a chest infection – never good for someone in the middle of doing the sodden summer festival rounds – which she then accessorised with an acne-like rash brought on by an allergic reaction to the penicillin she was taking.

And now, with her debut album released tomorrow, she has a certain east London running-and-jumping competition to contend with. "It's sort of annoying that no one's going to really care [about the album] because they'll all be watching fricking David Oliver," she chuckles, referring to the somewhat buff US hurdler, her interest in events stretching only as far as "a lot of very attractive athletes".

Plonking herself down in a chair, she proceeds to put her grumbling in context: "It's the story of my life… I am a pessimist, or I'd say realist, actually; I don't like to have rose-tinted glasses on everything – I'd much rather walk into a room and say I feel like this and like that – and hey!"

This breezy matter-of-factness is charming – I like someone dumping on the Olympics as much as the next bitterly ticketless Londoner – if unexpected. Put that down to the sleight-of-hand performed by the 21-year-old's scintillating singing voice. Slipping up and down the octaves, from a low drawl to a hyperventilated squeal, it's jarring, ethereal intensity doesn't prepare you for a natural natterer. Then again, the genesis of this inimitable instrument is more mundane than you might expect.

"When I started writing the album, I didn't have any strength in my diaphragm," she says. "I wasn't a formally trained singer and I hadn't been belting it out since I was four years old, so my voice was grumbly and breathy and croaky – all things I couldn't get rid of. But then I started realising there were a lot of 17- and 18-year-old girls being churned out by the major labels, and [my voice was] what marked me out."

Less mundane, thankfully, is the resulting music – a sultry kind of minimalist urban-pop, cavernous, crepuscular, and bearing the legacy of 1990s trip-hop. Beguiling enough in itself, when set against the endless thud of Euro-trance currently emanating from the charts, it's positively bewitching. Even more so because things could have turned out very differently.

When Stoecker signed to Atlantic Records, she was initially paired up with crack songwriters such as Robbie Williams' former right-hand man Guy Chambers and Rihanna/Beyoncé collaborator Kuk Harrell. But while many a young artist would have been overawed by such introductions, Stoecker quickly decided that such hit- factory songwriting wasn't her bag. "I learnt a lot from [their methods] but I couldn't connect with it… you know, that thing of, "Now we have a chorus, and then we need a major chord." I'd be like, "These are just my emotions, what are you talking about?"

But then, Stoecker has always been a few steps ahead of her peers. "I thought I was 25 when I was five," is how she describes her hippy-ish upbringing with her mum and DJ-cum-gig-promoter stepfather on a Camden council estate. While other kids were being reared on nursery rhymes and smiley potato faces, she was being weaned on Bob Marley and sourdough. And thanks to her step-dad's work, she got to toddle around the mid-1990s gigging scene like a miniature musical Zelig. Some of the deeply enviable memories she skips through include watching Oasis play an early gig at Camden's tiny WKD club and standing on stage with the Fugees at Wembley Arena. Oh, and then there was the time she had a sing-along with some old soul journeyman called Stevie Wonder in her gran's Ladbroke Grove living-room. Presumably she must have been the coolest kid in school, nay, the entire British education system? "No, people didn't know. Unless [you'd met] the Spice Girls or Five, no one gave a crap," she laughs.

Aged 12, however, the bohemian rhapsody came to a sudden end when her stepdad died in a car accident. "He was with me since the age of two; my whole everything changed," she says. "My mum went into complete shock and the whole house fell silent because every song reminded her of him. The only way there was going to be music in the house was if I wrote it."

And so it was that, with some cursory experience of the piano, she began to create songs from the simplest of chord patterns. Her album's second track, "Breathe", was written when she was 14; documenting her suffocating despair ("I must survive/this wonderful punishment called life"), it is the emotional centrepiece of a record which she says developed as an aural diary since she was "crap at keeping" the written ones.

Not that she kept this chronicle, either: a couple of years were lost to standard-issue teenage terror-dom – partying, truancy et al – and her chequered school attendance record meant she had to beg her way into an Islington sixth-form college by promising to reform her ways. Which, duly, she didn't – but with good reason this time: after songs she recorded for her musical performance A-level found their way from the studio producer to industry A&Rs, she found herself skipping classes for meetings with major labels. "I didn't really understand what was going on – I had no idea what a record contract meant. But the idea of getting some money from it, that was the thing I understood."

Though dammit if the joy of filthy lucre didn't quickly become adulterated by artistic concerns. As the title of the album, From the Roots Up, suggests, her talent has evolved organically over the past four years, refined by hard-won life experiences rather than cranked through the hype machine. Said events including a tumultuous relationship with a much older musician, her first proper love "who broke my heart a million and one times", and the death of an old friend in prison, which inspired the piano elegy "21". "He was in a bad crowd, but he was like a big brother; he always looked after me," she says. "I remember I was in New York, working. It was 3am and I was in the studio and I got a call from a friend of his saying he'd been in a fight and probably wasn't going to make it. It was going to be his 21st birthday a few weeks later, and that set me off – I had a beat left over from [our recording session] and I just started singing over the top of it. It was all done in a few minutes – it was the fastest song I've ever written."

Meanwhile, she served an apprenticeship of sorts as a guest vocalist for Chase & Status on a two-year tour, during which time the formerly underground drum'*'bass duo became teen-raver favourites the world over. And so, as well as learning how to project her voice to fill ever- bigger venues, she bore witness to the mixed blessings of mainstream success. "We started all packed together on one bus and by the time we finished, there were three tour buses and it was five-star hotels everywhere. It's funny, though, because in the beginning we were all a lot closer," she says with a note of suspicion. "All those other things give you the freedom to separate yourself from each other."

Conversely, a recent encounter with a bona-fide musical superstar, namely the artist formerly known as the Artist Formerly Known as Prince, was a lot closer than she might have expected. Impressed by her single "Love You So", the "Kiss" maestro invited her to support him on his recent Australian tour; that he did so with a personal phone call was a marker of his solicitousness. "You can be on the same bill as someone like that and never see them, but it wasn't like that at all," she says. "We hung out constantly, we watched TV and ate pasta and I had a jamming session with him in his living-room."

Though she wouldn't go so far as to call them BFFs, it appears she wields no little influence with the funky one. "I'm trying to get him to do Glastonbury next year and force them to have me second on the bill," she says. Was he convinced? (Prince Glastonbury rumours are, after all, as much of an institution as the festival itself.) "He did mention [it]. I think it would be amazing." So remember: you heard the entirely unsubstantiated but potentially mud-shattering scoop here first. And as to any pearls of wisdom he bestowed on her? "He did tell me, in a set for a bigger show, to cut out some of the slower-tempo songs and keep [the energy] up."

Now, I hate to question the wisdom of pop royalty, but really? You only have to listen to Stoecker's recent single "Inside My Love" to know that languor is the primary weapon in her musical artillery. A cover of the 1975 Minnie Riperton classic, it decelerates the already slow-burningly sensual original into a near-paralysed expression of carnal longing. Indeed, the album's vibe as a whole is what you might politely term "pre-coital", that is to say, "catch someone's eye while listening to it on public transport at your peril". Stoecker, for her part, claims its eroticism is mostly as unconscious as it is potent. "When people say, 'Delilah's quite a sexual artist,' I think, 'Really?' I would say I'm more about vulnerability and honesty but obviously the time when you are most vulnerable is during sex."

Furthermore, Stoecker has strongly resisted attempts to raunch up her image: despite recent forays into fashion modelling, she says she is "tomboyish" at heart – today she is wearing the grungy ensemble of lumberjack shirt, blues jeans, and Converse trainers – and recalls how she quickly rid herself of a "manipulative" manager who encouraged her to dress skimpily to get ahead. Though, by the same token, she is equally scathing about "musos" who would deign to patronise her when she chooses to glam up a bit. "I don't run around being like, 'I play everything, I write everything, I produce,' so when I'm on stage wearing big heels and my legs are out, they can sometimes assume I'm a pop puppet. If I looked like a dog a bit more, then I'd be an 'artist'," she complains.

After more than two hours in her engaging, opinionated company, it's clear there are no strings attached here. As for her expectations for the album, she remains circumspect. "I'm not hugely marketed. If I was, there'd be the pressure to sell and I don't know which is better – to have that or just see what happens."

Though, try as she may at times, this self-styled pessimist can't quite disguise a tungsten self-belief. "I guarantee that person will have a very different opinion soon enough," she says, vis-à-vis a bitchy recent review. "I know it because I know that what I do, I'm good at it. It's not for everyone, but you can't deny I'm doing something different, and if you love music and respect music, you have to respect difference." And so say all of us.

'From the Roots Up' is out tomorrow on Atlantic