Descriptions of Nicola Sturgeon swing between those appropriate to a celebrity in Hello! and to a seasoned political heavyweight. The bright future of the Scottish National Party, it has been said, doesn't smile, opposes privatised healthcare, is a "nippy sweetie" (an irritable, sharp-tongued person) and Scotland's footwear rival to Imelda Marcos. But the reality of the Scottish Parliament's Deputy First Minister is that she is not a woman to be taken or treated lightly. She prefers serious political debate to questions about Christian Louboutin v Jimmy Choo. Lifestyle fluff is not Sturgeon's style.

Sturgeon is an influential figure, especially as the country pushes harder for independence, as both Deputy Leader of the Scottish National Party and Health Secretary. She has arguably never had more on her plate, with Scotland making headlines over its funding of the swine flu vaccine and for its dealings over the Lockerbie bomber. Sturgeon, born in Irvine, North Ayrshire, in 1970, claims to have grown up in the "dark days of the Thatcher era". But she is keen to play down her childhood, like most of her personal life. "I grew up in a fairly standard, normal, working-class family. It was a fairly unremarkable childhood. I didn't have any particular political background in my family, although I later found out that my grandfather had been a party member back in the 1960s. Must be something in the genes."

The politics of the SNP inspired her at an early age. She joined when she was just 16 and got her first taste when she campaigned for a local candidate in the 1987 election. "What made me join was a conversation with my English teacher, who was a Labour councillor," she reveals. "He knew I was interested in politics and assumed without even asking me that I would join the Labour Party. He actually brought me a membership application form. That was the catalyst. I thought: ‘Stuff you, I'm going to join the SNP.'"

Her upbringing does not seem to have naturally steered her towards the party, though. "Obviously, I was vehemently anti-Tory at the time," she says. "Kinnock was leader of the Labour Party and, although everything in my background might have suggested that I would have gone into the Labour Party, it just didn't feel right to me."

After school, Sturgeon studied law at Glasgow University. Her real involvement in the SNP student wing took off here. "I spent more time involved in politics than I did studying law," she says. But she managed to get a diploma in legal practice and went on to work as a solicitor in Glasgow. Why didn't she try for a political career from the word go? "Remember, back then, there wasn't a Scottish Parliament. And the SNP, while a big force in Scottish politics, wasn't the force it is today. The idea at that time of a career in politics was not impossible, but it was always a long shot. But when the Scottish Parliament came along, the opportunities changed quite dramatically."

With a family that was not overtly political, who inspired Sturgeon's interest in politics? Internationally, she admires Nelson Mandela as an "absolute personification of good triumphing over evil". Domestically, she cites nationalist icon and MP Winnie Ewing. "She was a member of the House of Commons at a time when there were very few women members and she was the only nationalist. She got a dreadful time down there. I mean, a really dreadful time. She would tell stories of being physically abused by other MPs. When I was growing up, I found - and still find - her ability to go through that, to still get her point across and her voice heard, really inspirational."

It was around the time that Winnie Ewing was ploughing her lonely furrow that Sturgeon met another huge influence on her life: her future partner Peter Murrell. They were introduced when she was just 18, at one of the party's youth weekends in Aberdeenshire, which Murrell organised. However, they only "officially" became a couple in 2004, when their relationship was made public at an SNP conference. Murrell is now SNP chief executive. One of the party's most influential figures, he has also been credited as one of the reasons behind first minister Alex Salmond's success.

One Scotsman journalist suggested that he has always been a "sensible man", with a likeness to Penfold from the children's cartoon Danger Mouse. But Sturgeon won't be drawn as to whether her partner is man or mouse. "I tend to think your private life should be off limits, unless there's a conflict between it and your public life. But I'm realistic enough to know that sometimes that isn't always the case, and I don't get particularly worked up about it."

Avoiding the emotional stress of working in a profession where press intrusion comes with the voting papers has not always been Sturgeon's forte. Dubbed a "nippy sweetie" by the Scottish media, it was widely reported that Sturgeon underwent a makeover to revamp her image before the 2007 Scottish election. Stylist Monica Loudon supposedly offered the MSP advice on what to wear during the campaign, and certain Scottish political commentators noted a change in Sturgeon's demeanour.

While she denies that she consciously sought to reinvent her look, she admits that she has loosened up. "I think that any woman would recognise that as you get older, you do certain things that you didn't do when you were younger. You dye your hair. But there was no sort of conscious restyling or revamp. People say: ‘You seem much more relaxed than you did 10 years ago'. My answer is: ‘Well, I am'. It is partly because you have a bit more confidence in your own abilities. You can learn to judge when you should get worked up about something, and when you shouldn't."

Sturgeon has had a lot to be worked up about recently. Scotland received international criticism for its controversial decision to release Lockerbie bomber Abdelbaset Ali al-Megrahi on "compassionate grounds". President Obama expressed his disappointment in al-Megrahi's release. But Sturgeon believes Scottish justice minister Kenny MacAskill made the right decision by returning al-Megrahi to Libya. She also points out that international figures such as Nelson Mandela strongly endorsed the Scottish Government's decision. However, she confesses that the judgment was "one of the most difficult decisions any minister has had to take".

She goes on: "Whatever way that decision had gone, some people would have passionately disagreed with it. I totally understand the point of view of people, either in this country or in America, particularly those who lost relatives in what was the most horrific crime imaginable. I understand how they feel. Had the decision gone the other way, there would have been people, including relatives in this country, who felt as pas-sionately that the decision to keep him in jail was the wrong decision."

Sturgeon is not afraid to be controversial when she feels passionately about something. Back in July, she was accused of playing politics over vaccination funding when she suggested that Westminster should pay for Scotland's swine fl u jab. She says this position is exactly the same stance taken in the Welsh and the Northern Irish assemblies. "The vaccine is going to happen and it is going to be funded," she explains. "It will be thrashed out one way or the other. If it is not funded by a UK contingency fund, then it will be funded by the Scottish Government."

Disagreements between the UK Parliament and the Scottish executive do seem to expose the fragility of devolution, especially with unforeseeable costs such as swine flu. Sturgeon is a militant supporter of Scottish independence, and is campaigning with the rest of the SNP for a referendum on the issue next year. She believes Scotland would vote for self-rule, contradicting a 2008 poll in The Herald, which found 50 per cent would vote against independence in general, while half of those polled would vote in favour of Scottish independence - if there was a Conservative government in power at Westminster.

Does this mean that the SNP will back David Cameron at the next election, then? "Er, no," Sturgeon replies. "I don't want to see a Tory government, but I don't particularly think that this last Labour government has done much for Scotland. At the end of the day, I want to see Scotland well represented, have its voice heard and have as much influence as possible.

"It may be a bit biased but that means having as many SNP MPs down there as possible. I think Scottish independence will not happen because somebody in London tells us that we are allowed to have it. It will happen when people vote for it." What if the SNP convinces the Scottish Parliament to hold a referendum and it doesn't go their way? "I am not really in the business of hypothesising on the basis of failure," Sturgeon retorts tartly.

With a life dominated by the fight for Scottish independence and the social bubble that accompanies politics, Sturgeon takes comfort from more simple things in her spare time. She enjoys the theatre, although "not as often as I'd like to", and has a passion for reading. "At the moment, I'm reading Team of Rivals, the biography of Abraham Lincoln. I've also just read Lincoln by Gore Vidal, so I'm on a bit of an American Civil War kick at the moment."

And yes, those shoes. Sturgeon admits to owning an infamously large collection. "I love shoes - they're a particular weakness. I tend to wear high heels because I'm not the tallest of people, so it gives me added height." But her quest for a few extra inches can have its down side. "I was at the opening of part of a hospital last week, and some podiatrist or chiropodist started to lecture me about the fact that I was wearing high heels!"

With a high-profile position in the party, as well as the health brief, Sturgeon's CV makes her one of the most likely candidates to stand for future leader. Indeed, she embarked on a campaign for the post fi ve years ago. But her rise to power has not always been easy. In 2004, she stepped down from the leadership bid, to run on a joint ticket with current SNP leader Alex Salmond. The media claimed this was because she was unlikely to beat her contender Roseanna Cunningham in the polls.

Sturgeon says that she changed her ticket far too early for anyone to know how it would have worked out. "Sure, you'll read things that say Roseanna would have won; you'll read things that say I would have won. Who knows? We'll never know now." But she adds: "I'm confi dent - you'll say I would say this - if I had stayed in the race I would have triumphed." Sturgeon is clearly still ambitious. But it is apparent she has learnt the hard way how expressions of ambition can be misinterpreted. Even when asked direct questions on the issue, she moves into ultra-cautious mode. Does she still have ambitions to become party leader? "I am not going to sit here and say, ‘No, absolutely not.' But we have a very strong and dominant leader of the SNP, who in my view is doing a fantastic job as fi rst minister. There is no vacancy, and I don't foresee a vacancy there for some considerable time."

But she adds: "If there is ever a vacancy for the leadership of the SNP, and I feel at that time that I've got something to offer it, then of course I would be interested," adding quickly, "but we are a long way off from that."

And with Salmond's popularity it could be a long time before she could take the reins in the SNP's battle for independence. "Character traits or approaches to the job that would be seen as strong leadership and ambition in a man, can be seen as off-putting traits in a woman," she says. "We are judged by different standards and that can make it harder. In my experience, from women politicians that I know, I think there is a feeling, subconscious as well as conscious, that we have to be that wee bit better, work that wee bit harder to really make our mark."

Does she feel that she has made her mark yet? "If I do nothing else in politics, the opportunity to be Deputy First Minister in the firstever SNP government and get the opportunity to be Health Secretary, that is enough for me frankly." But you get the impression that Sturgeon does want more. She will probably get it too, with her personal mix of ambition, intellect and caution. You sense she has more challenges she wants to confront, more issues to address that ultimately can't be satisfi ed from a position of Deputy First Minister. Quizzed on how she wants to be remembered, she simply says: "Ask me that in another 40 years. I'm sure all my best work is ahead of me."

Tags: Interviews, Issue 17, Nicola Sturgeon