STARDOM hasn't quite found KT Tunstall yet, but it will have claimed her by the year's end. Already, it's licking at the edges of her life, inching towards her with the unstoppability of a glacier. "It's been amazing, really amazing . . . and it's only spring, " beams the 29-year-old Fifer when I ask her about her year so far. "The highlight is that every show is selling out and I don't have to photocopy flyers and hand them out and beg people to come like I used to."

There are also more interviews, bigger and better venues in which to deliver the music she calls "girl folk with attitude" and more generous praise to savour as a result.

But, she adds: "I can still go down the tube and walk past my poster and nobody knows it's me."

That those same posters are seven-feet tall highlights the faith her record company has in her.

Clearly, they think they're on to a winner.

Those who have heard Tunstall busking in coffee shops and pubs over the years - in Stirling's Beanscene, perhaps, or the West Port bar in her hometown of St Andrews - will no doubt concur.

But for the general public the eureka moment came last October when she stepped on to a BBC soundstage as a last-minute replacement for rap superstar Nas, who had been forced to pull out of an appearance on Later With Jools Holland.

Tunstall, on tour at the time playing flute in a friend's band, was told she had 24 hours to get down to London.

"I came back overnight on the tour bus. Everyone was drinking till 3am and it was all pretty crazy. I got home, had a bath, went to the BBC, then next thing I know I'm sitting watching The Cure, going, 'I think I'm on next.'" Since then the carousel hasn't stopped. Audience response to Tunstall's Later performance was ecstatic, the song she performed was hastily added to her then-unreleased debut album and a November tour sold out. The album, Eye To The Telescope, followed a month later and a further tour in February also sold out. Last month she performed in New York in a customised kilt as part of the Tartan Day celebrations, next week she releases a new single and later this month she plays Glasgow's Carling Academy. After that there's the small matter of appearances at T in the Park and Glastonbury.

KT Tunstall - or Katie to use her given name - will have turned 30 by the time she steps out for her summer festival shows. Her age lends her lyrics a certain maturity, but it also hints at the struggle she has had to bring her music to the audience she always thought it deserved. She may have burst into the national consciousness, but behind her rapid rise are years of toil, unemployment and conflict.

Born in Edinburgh and adopted at just 18 days old, Tunstall has also made discoveries along the way, notably about the identity of her birth mother.

And against the background of her gathering fame, her search for her real father continues.

We meet at a recording studio in a leafy west London suburb, where Tunstall is recording a threesong session and an interview to be streamed on the internet for AOL members. The control room is crowded and there's a buzz in the air as she picks up her acoustic guitar to perform.

Afterwards, she settles into a plush leather sofa to chat. Talk soon turns to home and her childhood in St Andrews. Her father was a physics lecturer at the university and her mother a primary school teacher so the Tunstall household - Katie and her brothers Dan (who is profoundly deaf ) and Joe - was nurturing and bookishly bohemian.

"My mum's very creative. She wrote a kids' book about the story of St Andrew and was always coming up with creative projects for us. If we were moaning that we were bored she'd wheel out paints and bits of junk and get us to make stuff."

Oddly, it was a world which was largely musicfree. "My parents weren't into music. We didn't have a stereo. There was a tape player and I started listening to tapes when I was about 15. I had an impulse to play music from a very young age and started playing piano when I was about six, started flute when I was 11, did my grades, did all the classical stuff then started writing songs at 15 on piano - cheesy as hell, really horrendous."

Tunstall attended Madras College in St Andrews but left on her 17th birthday because she wasn't allowed to do art and music in the same school year. She went to Dundee High School instead, then landed a year's scholarship at a Connecticut boarding school. Next stop was Royal Holloway College in London where she studied theatre and music. She completed her degree, but found university an uninspiring experience.

"It was on a campus and it wasn't what I had expected. I had a lot of fun and drank a lot but I was expecting to find this Shangri-La of incredible musicians. All I found was one banjo player, who was very good, but it wasn't quite what I wanted. So I went home again."

Returning to St Andrews, Tunstall lived, loved and made music with a group of musicians she had first met at school. Among them were the three Anderson brothers - Gordon, Kenny and Ian - and Steve Mason who, along with Gordon Anderson, formed The Beta Band in the late 1990s.

"I was singing with Kenny when I was 16, 17. I went out with Ian for a couple of years and we lived up a hill in a little cottage with no heating and a dog and a fire, stealing vegetables from local fields with not a f***ing penny to our name, just gigging and writing.

It's easy to have rose-tinted glasses about it now - because there were times when it just got too hard - but really it was a pretty blissful existence."

Unfortunately, her parents didn't agree, though their opposition just strengthened Tunstall's determination to succeed. "I really needed that wall to push against. All my friends were saying, 'You're great, you should do well', and it's easy to leave it at that. But your parents remain the two people you want to impress the most on the planet and I desperately wanted them to be proud of what I was doing. So it was a matter of pride and determination - I thought 'I've got to make it work'."

Eventually she decided to break away, leave Fife and Scotland and head back to London. It wasn't an easy decision. "I was very reticent about coming to London. I was kind of pissed off about it. I felt very vexed that I spent six years gigging in Scotland and couldn't get arrested . . . I suppose I had a compulsion to get my music to more people. I did want to make more of a living out of it. It wasn't financially driven, but it was definitely a part of it."

Ironically, the East Neuk music scene Tunstall left behind has since blossomed. Gordon, Kenny and Ian Anderson all have solo careers - as Lone Pigeon, King Creosote and Pip Dylan respectively - and perform under the umbrella title The Fence Collective. Kenny Anderson appeared in Edinburgh last week as part of the Triptych festival. There's also a record label, Fence Records, for the brothers' collective output. Meanwhile, another St Andrews band, Dogs Die In Hot Cars, are being touted as the new Franz Ferdinand.

In person, Tunstall oozes confidence, coming across more like a sparky children's television presenter than a musician taking her first steps to stardom. She only falters - and then only slightly - when the subject of her family background comes up.

She always knew she was adopted. "I knew before I could speak, " she says. "My parents were straight down the line about it." But after seeing Mike Leigh's film Secrets And Lies, in which a young black woman seeks out the white mother who gave her away, she decided it was finally time to uncover the identity of her birth mother.

"I thought, 'Right, I could handle it.' I just felt ready, " she says. What she discovered was that her mother had been in Edinburgh the whole time - and she was half Chinese. "Her mother is Cantonese and she was born in Hong Kong but she grew up in Scotland."

Over the years since the discovery, a friendship of sorts has developed between the two women.

"We're getting there, " says Tunstall, a little guardedly. "As you can imagine you can't develop a relationship with someone who is your mother but who is also a complete stranger in a short period of time. We're just enjoying it. But it's a completely different relationship from the one I have with my family. I'm glad it's there though."

As for her father, the trail has gone cold. Tunstall's birth parents aren't in touch with each other any more and, while she has some details about her father, she has no firm leads.

"I've got quite a lot of information but it's just not come up with anything. It's not a big deal really. As a child it probably is, especially when you find out the circumstances of your adoption. But it's more intriguing for a kid to find their mum. That's who gave birth to them and often that's who's made the decision to give the kid up for adoption."

I ask her if she knows what those circumstances were. "She was just a woman who wasn't in the state of mind where she could bring up a kid, " she says.

"But that's her story, not mine."

Quite so. And, as fame inches ever closer, KT Tunstall's story is just beginning.

KTTunstall's new single, Other Side Of The World, is released on May 9 and she will appear at the Virgin Megastore, Buchanan Street, Glasgow on the same day at 6pm.

She also appears at the Carling Academy in Glasgow on May 25 www. kttunstall. com