On May 6, 1999, voters in Scotland went to the polls to elect the first Scottish Parliament in 300 years, entrenched around the principle that the people were sovereign.

129 MSPs, elected by proportional representation, would carry not so much the hopes as the demanding expectations of an excited nation.

The first Deputy First Minister of Scotland, Liberal Democrat Jim Wallace, said there was "a degree of excitement and a degree of over expectation" over the possibilities for the new institution, which he said would not be "the parliament on the Thames translated to Edinburgh".

Scotland had voted 'Yes, Yes' in a referendum in September 1997 - Yes to a Scottish Parliament and Yes to it having tax-varying powers.

When the Bill paving the way for Home Rule was introduced, the Secretary of State for Scotland, Donald Dewar, declared: "Clause one of the bill could not be clearer. There shall be a Scottish Parliament. I like that."

The story of the first Holyrood election campaign and forming of a government is told in a special 20th anniversary programme, Vote 99 - Birth of a New Scotland, available on the STV Player from later today.

Dewar's special advisor Wendy Alexander points out that the parliament was born out of a long struggle for some sort of self-government culminating in the meetings throughout the 1990s of the Scottish Constitutional Convention, the body that produced the blueprint on which the parliament was based.

"I think the campaign for a Scottish Parliament was a big tent, big umbrella, everybody was part of it," she says.

Before the campaign started in earnest, a foreign affairs issue drew clear lines between the leaders of Scotland's unionist parties and Alex Salmond of the SNP.

In March of 1999, NATO launched Operation Allied Forces, a sustained campaign of aerial bombardment aimed at disabling Serbian aggression in Kosovo which had seen repeated attempts to 'ethnically cleanse' Kosovar Albanians.

The SNP leader, in a televised broadcast, described the action as one of "dubious legality but above all one of unpardonable folly". Given the horrific images coming out of Kosovo, Salmond's opponents sensed a misjudgement.

Former First Minster Jack McConnell says: "He went too quickly with language that was too extreme and put himself out of touch with public opinion."

The current First Minister has a more nuanced view of the broadcast and the ensuing furore. Nicola Sturgeon says: "The headlines were about supporting Milosevic, the toast of Belgrade and that is how people then judged the argument, and so in a sense it was the characterisation of what he said that became the issue. Did it change the outcome of the election? I don't think so."

Scotland's political parties squared up to one another for the first elections. The Labour campaign centred on Donald Dewar, a veteran of Home Rule debates and a moderate social democrat who described his politics as about "righting the social arithmetic", by which he meant smashing the factors that condemned children to poverty.

Wendy Alexander says: "Donald really spent the campaign out on a bus touring the entire country being with people, talking to the people whose national leader we hoped he was about to become."

The Labour manifesto offering was cautious in what appeared to be a strategy of playing safe, McConnell saying: "I think it was quite hard for Donald Dewar to strike out a completely fresh approach for the 1999 election because Labour were in government (at Westminster) and they had started a programme."

Senior Labour figures knew that the party was unlikely to control the new parliament as the proportional voting system would deny Labour its usual stranglehold.

Alexander points out: "In the Labour party we were acutely aware that having won so decisively in the UK, we were actually giving power away by committing ourselves to PR."

It wasn't just the voting system that could reign in Labour expectations. McConnell, long associated with his party's nationalist wing, argues that in devolved or federal systems, parties who embrace identity politics, whether it be Bavaria, Catalonia or Quebec, tend to do well. On that basis "we were braced for a tough fight", says McConnell as the SNP stepped up the argument they and they alone were 'Scotland's party'.

The Kosovo fallout had subsided by the time the SNP launched their manifesto based on "enterprise, fairness, democracy".

"We thought we could win the election," says Nicola Sturgeon, before conceding that this has been a common feature of the pre-election mood in the SNP during her lifetime. She concedes with hindsight that the chances of an SNP victory were "slim".

The Scottish Liberal Democrats offered an expanded rail network, more renewable energy provision and pre- school education for three and four-year-olds. But journalists were only interested in an answer to one question: Would the Lib Dems do a deal with Labour and form a coalition government? Two decades on, Jim Wallace reflects on the media portrayal of himself as the Kingmaker. He says: "I argued, no, I'm not the Kingmaker. The electorate are the Kingmakers." It was a line that he stuck to doggedly.

The Scottish Conservatives were contrite by 1999. Edward Heath's declaration of Perth in 1968, committing the party to devolution had been torpedoed by Margaret Thatcher in the 1970s. She wore her Unionism with attitude and blocked repeated demands for a parliament, much to the chagrin of Scottish voters who greased the slide in electoral fortunes for her party.

The Conservative manifesto was the ultimate in mea culpa, mea maximum culpa. Annabel Goldie recalls the bluntness of the foreword to the Tory manifesto: "On the 1st of May, 1997, the people of Scotland told us what they thought of the Conservatives. We got it wrong." Goldie says the Conservative campaign was about "reassuring voters that we were now signed up to the new political Scotland".

The new political Scotland would also find a voice for the Scottish Greens and Scottish Socialists. The eminently reasonable Robin Harper and the charismatic Tommy Sheridan would lead the charge for parliamentary representation.

Labour had one legacy problem, emanating from its ham-fisted and utterly counter-productive system for vetting potential parliamentary candidates. In its wisdom the party refused to endorse the Falkirk West MP Dennis Canavan as a potential candidate. The respected MP quit the party and stood as an independent. A life-long supporter of Home Rule, the wrench for Canavan in abandoning Labour was obvious to see.

He reflects: "I had the support of over 97% of party members in my constituency on a one-member-one-vote basis and yet you had this situation were three men and a dog could outnumber all of my constituency party members." The decision by Labour to assassinate Canavan would rebound spectacularly.

As the campaign progressed the polls pointed to Labour being the largest party. The post-1997 glow was still palpable. Wallace concedes: "There was still an aura about the Blair government which was bound to translate itself to Scotland."

The SNP's answer to being behind was to gamble by backing a tax increase for Scots. The 'penny for Scotland' policy would effectively cancel a tax cut given by Labour in a pre-devolved setting.

Andrew Wilson was a rising star in SNP circles and a trusted Salmond advisor on the economy. "I think it certainly got cut through," he says. "I think the mistake was that we hadn't really articulated what we were going to do with the money."

Sturgeon concurs with this view, adding: "It is a matter of opinion as to whether the Scottish electorate were ready for that argument."

The most difficult and the lowest point in the campaign for the SNP came when they released a document on the economics of independence. Repeated questions at a media conference on the detail of their prospectus had Salmond and Wilson on the back foot. Described by Sturgeon as the "calculator moment" and "not our finest hour", a journalist from the Financial Times was dogged in trying to establish what kind of deficit an independent Scotland might run.

Television pictures showed Salmond and Wilson desperately trying to calculate figures off the top of their heads. "It did not look orderly. It was not professional. I don't look back on it with fondness," says Wilson. For Alexander it was a telling moment. "I think it was a turning point," she says. "When it came to judgement on economic plans, on that occasion they simply were found wanting."

Towards the end of the campaign, McConnell says that the Labour rhetoric had one eye on what they might have to do to forge a deal with the Liberal Democrats and that meant not having tuition fees in Scotland, thus embracing a policy that was being championed by Tony Blair in the rest of the UK.

McConnell observes: "That was when divisions started to appear between the Labour Party in Scotland, who were trying to deal with the reality of the situation, and the Chancellor and others in Westminster who were a bit more nervous about the situation."

The electoral system guaranteed that this would be a "something for everybody" election and so it proved.

Labour won 56 seats, against 35 for the SNP, 18 for the Conservatives, 17 for the Liberal Democrats, one each for the Greens and Scottish Socialists and, in the biggest triumph of Vote 99, Dennis Canavan won with the largest majority in Scotland in Falkirk West.

Turnout, somewhat astonishingly, failed to hit 60%. Canavan, recalling the campaign, says: "I think nationally it was a bit flat to be honest. I don't think any of the party leaders fought a hugely exciting campaign."

Both Sturgeon and Wilson recall a tinge of disappointment. The current First Minister failed to win Glasgow Govan. "You are always fighting to win," she says. "So when you don't there's a sense of disappointment. But looking back it was probably broadly the result we were going to get." Wilson recalls being a "wee bit disappointed" but took comfort that it felt really good that "a substantial opposition group went into Holyrood".

To the victors, in so far a PR allows it, the spoils. Donald Dewar and Jim Wallace set about negotiating a coalition. Both party manifestos were scoured for common themes and policies.

Wendy Alexander recalls a moment of levity when Dewar asked Wallace: "What piece of Liberal nonsense is this?" Dewar emerged deflated when Wallace pointed out the proposal was from Labour's manifesto.

The talks moved slowly and Wallace is adamant that coalition "was not a given". They even hit problems. Wallace was concerned by a small but potentially troublesome group in his own party who wanted a confidence and supply arrangement rather than a full collation.

He recalls: "I can remember at least two occasions during the coalition talks when I folded over my notepad and said, 'well Donald, I think we have given it our best try. I just don't think this is going to work'."

When the now Lord Wallace of Tankerness talks of this two decades later, you get the distinct impression this was for real and not a fit of melodrama calculated to win a negotiating point.

Interesting that history could have panned out differently had Dewar and Wallace not eventually been able to forge a coalition programme for government.

In a sense the real historical significance of 1999 is that the constitutional genie was out of the bottle. There was no going back. In the next two decades, public policy north and south of the border would diverge without the new institution looking over its shoulder at what the bigger legislature was doing.

The much-heralded consensus politics failed to arrive, proving largely the late Scottish Tory leader David McLetchie's point that the essence of politics is conflict.

The last words go to my guests in this retrospective.

Andrew Wilson described the election of the first Scottish Parliament for 300 years as "a wonderful time - it felt like you were involved in history happening".

Annabel Goldie says the Conservative objective "was to bring some fresh thought" in public policy.

Jack McConnell believes that in their own ways all of the First Minister's have spoken up for Scotland at different times.

Both Jim Wallace and Nicola Sturgeon say it is unthinkable for Scotland not to have a Parliament and that in a very real sense is its crowning achievement.

I finish with the words of the late Donald Dewar. He described devolution as "a process not an event".

The last 20 years has proven the redolence of that observation.

The special programme, Vote 99 - Birth of a New Scotland, will be available on the STV Player from later today, while an abridged version will appear on Scotland Tonight on STV at 10.40pm.