GORDON BROWN be warned. Alex Salmond is keeping a diary. Every anti-Scottish remark, every secret deal on transferring prisoners, every intelligence cock-up over airport security is being recorded for posterity. "It's a brilliant read," he says with characteristic modesty.

Well, I suppose he's got a lot to be immodest about. Salmond has done more in his first 50 days than his predecessors achieved in 150, and to unprecedented acclaim from the Scottish press. In the parliamentary recess, the new first minister is touring Europe to spread the news.

Standing anonymously in the concourse of Edinburgh Airport with their entourage of young female civil servants, the Salmonds look a bit like a family off to attend a wedding, Salmond's wife, Moira, carrying a posh hat in a big box. "John F Kennedy used to introduce himself as the man who accompanies Jackie Kennedy," the first minister remarks. "I'm the man who accompanies Moira's hat." Just as well too, because their luggage goes astray and they arrive in Brussels accompanied only by Moira's hat. Fortunately, it's the most important piece of kit, since they are meeting the Queen, for the 90th anniversary of the battle of Passchendaele.

It's Salmond's fourth close encounter with royalty and he is very proud of his good relations with the Queen, and with Prince Charles, who was instrumental in getting Dumfries House and its contents saved for the nation, with a little help from Bute House. Salmond intends to go through the formal ceremony to become a privy counsellor in a couple of weeks. "All that walking backward and garters? Aren't you worried you're becoming a part of the establishment, seduced by the embrace of monarchy?" He doesn't rise to it, saying the Queen understands the Scottish Question a lot better than her government. "She knows a Scot became the King of England."

For a political leader with a 24/7 schedule, Salmond is intensely relaxed. He is the virtuoso of just being there. Whether it is laying wreaths with the Queen at the Menin Gate or sitting in the airport bus in Edinburgh, exchanging banter with passengers, Salmond has an ability to adapt to his surroundings and appear to dominate them without really doing anything.

The first minister is a big man - though, with a rigorous diet, trying to get smaller - and he is renowned for having an ego to match. But Salmond seems completely uninterested in the trappings of power or celebrity, and doesn't appear to have any particular sense of his own personal importance. One of the most intelligent politicians of his age, he has the gift of normality.

There's no media fanfare associated with his inaugural trip to Brussels, his first overseas engagement since he became first minister. No motorcades or fancy dinners, just a sweaty reception at Scotland House - a pokey corner of an anonymous Brussels block - with the usual tartan tat of whisky and pipers. Salmond works the room, mainly lower- order bureaucrats, some business types and local Caledonian societies. "The Scotteratti", Salmond calls them. "But don't underestimate the networks of Scots expats. They are a very valuable resource, they know everything that's going on here, and they tell us".

When Salmond gets up to speak no- one expects more than a few pleasantries, least of all Michael Aron, the senior Scottish Executive civil servant whose internal memo about Scottish ministers being kept in the anteroom during UK-led European delegations was leaked 18 months ago. Officials tell me that Jack McConnell hardly ever spoke at events like these, worried about charges of getting above himself and preferring to merge into the crowd. But Salmond is all about getting above himself and he doesn't do merging.

The first minister launches into a blatantly political speech, declaring: "I believe that it is time to transform the nature of Scotland's representation and impact in Europe tonight, my message is clear and unambiguous - this is the time for Scotland to assume our obligations and responsibilities and to help mould the world around us to rediscover the sense of internationalism which once defined our nation."

The Eurocrats look slightly bewildered by Salmond's Brussels declaration. This wasn't a political event, and there was no-one of any importance present. Not even the Scottish press, who gave up attending these things because nothing happens - except this time. For Salmond is making clear this goes way beyond taking the lead in fishing talks. On issues from energy to financial services, if the first minister means what he says, Scotland will no longer adopt the agreed UK negotiating position, but will increasingly pursue an independent line in Europe.

The officials from the UK office in Brussels certainly got the message: "This is really heavy," says one. "If the Scots are going to start making their own policy here, then there could be tears before bed." Later, I ask Salmond why he didn't seek a bigger build-up to this milestone address. "Some things are better understated," he says. "Such as: We hold these truths to be self-evident.'" Hmm. I don't recall Thomas Jefferson delivering the American Declaration of Independence over warm wine and canapes.

How does he respond to the charge that he was getting above himself, exceeding his authority? After all, as a minority leader in a regional parliament, how can he unilaterally alter Britain's constitutional relationship with Europe? There is no machinery for Scotland to be independently represented. "We'll see. I think the people here realise what we are about, and that Scotland's interest has not been articulated in the past. It's not actually about independence. Look at Flanders, which leads for Belgium on fishing talks." Indeed, the Länder regional governments in Germany mostly have their own independent representation in Europe, as do autonomous Spanish provinces like Catalonia.

It takes supreme self-confidence, not to say brass, to get away with this kind of thing. Any less secure politician might have feared being laughed at. But Salmond gets away with it because of his immunity to ridicule and self-doubt, because of the prestige he has built in his short spell in government, and also because he can speak intelligently and with a passion that belies the formal limits of his political power.

As with his minority administration in Holyrood, which has no visible means of support, people suspend disbelief. He sounds like the real deal. Influential people may not have been listening to him in Brussels, but lots of their officials were - the Brussels "bureaucrati" - and they seemed impressed, excited even.

Next day, Salmond did a round of engagements with European commissioners, including Peter Mandelson, one-time New Labour "prince of darkness", and now the commissioner with responsibility for world trade. Salmond claims to have struck up an instant rapport and to have achieved "a result" over the problem of Norwegian salmon dumping. "I've a lot of respect for Peter Mandelson and what he has achieved," he says, utterly straight-faced. "Actually, I asked him if he was writing a diary. He said, not one like "that"' - meaning Alastair Campbell's - which he says he hasn't read." Salmond makes a virtue of being on improbably friendly terms with everyone he meets, and it seems to work. "I'm not here to pick fights," he says.

But is he going to pick a fight with Gordon Brown? Tomorrow, on the next leg of Salmond's grand tour, the first minister will be face to face for the first time with the new prime minister. The occasion is the British-Irish Council in Belfast, where Salmond joins the leaders of the other devolved parliaments and assemblies.

It may not be on the agenda for tomorrow's meeting, but there is no doubt that Salmond is very interested in getting access to the £1.5 billion in unspent Scottish End Year Flexibility cash which he says is sitting in the Treasury because Labour failed to make any use of it over the past eight years. "Scotland is treated with less responsibility in its financial affairs than a lunatic, a bankrupt or a minor," he says. Unlike a lowly local authority, the Scottish Executive cannot borrow money, or even take charge of its own unspent revenues, Salmond complains.

And, of course, there is the matter of attendance allowances for older disabled people, which were withheld by London after the introduction of free personal care. "It's a mad mechanism," Salmond says, "The idea that you can't change policy in Scotland for fear of losing funding is outrageous." Labour MSPs in Holyrood are convinced that London will similarly refuse to keep paying £380 million in council tax benefits if and when Salmond abolishes the council tax. But the first minister isn't so sure they're right. He believes that Brown will allow payments to be maintained through the Barnett Formula and the funding mechanism because the last thing Downing St wants is a row over Scottish spending.

Intriguingly, Salmond believes he is close to achieving a modus vivendi with the prime minister, largely through the way in which the governments co-operated over the Glasgow Airport attack. He has made a point of setting aside the row over the transfer of Lockerbie bomber Abdelbaset Ali Mohmed al-Megrahi which Number 10 now accepts was discussed during Tony Blair's meeting with Libyan leader Muammar Gaddafi in May. Salmond says he deliberately didn't depart from the "Britishness" agenda that Gordon Brown raised in the aftermath of the failed terrorists bombings. Nor did he rise to the challenge when he was briefed against for saying that the terrorists weren't Scottish.

Clearly, there is mutual respect here; something that makes Salmond think that he can do business with the new PM. I ask: "What's the difference for you between dealing with Brown and Blair?" The answer is surprising. "Well, I wouldn't lie to him," says Salmond. "Would you have lied to Blair?" "No, though I didn't really get the chance, since we didn't talk, but I wouldn't have trusted him." Perhaps because Brown, unlike his predecessor, understands devolution and understands Scottish politics, Salmond thinks relations will be better.

Chance would be a fine thing. The reality is that Salmond and Brown are deadly enemies, who will look to every opportunity to outsmart each other. There is an epic quality to this confrontation between the two most powerful Scottish politicians of their generation: the lad o' pairts versus the son of the manse; the quick-witted iconoclastic Scottish radical versus the strict and moralising dominie.

And what an extraordinary stage on which to hold their first skirmish - in Belfast, presided over by the former megaphone of militant Protestantism, the Rev Ian Paisley, and the Republican nationalist, Martin McGuinness. When Gordon Brown supported devolution all those years ago, did he ever think he would preside as prime minister over a gathering like this? With a nationalist first minister of Scotland and a nationalist acting first minister of Wales?

Salmond was joined at the Menin Gate memorial by Ieuan Wyn Jones, of Plaid Cymru, who is co-leader of the new Labour-nationalist coalition in Cardiff. They discussed matters of common interest - in particular finance and how to strike a better deal for the national parliaments in their dealings with London. The whole issue of joint sub-committees between Holyrood and Westminster is on the way to being resolved. Mind you, the question of separate Scottish representation in Europe certainly is not. The government line remains that Scotland is best represented by the UK in Europe, because that way it gets listened to, and there is no prospect of there being any change in the constitutional relationship with Brussels - so watch this space.

Salmond returned from his Brussels expedition claiming to be well satisfied with the response. But in the end, what has actually been achieved? A change of tone, certainly, and some big talk - but can Scotland really play in the Euro-league?

Like everything Salmond does right now, his Brussels trip was an exercise in improvisation, riding on the back of an official engagement. Salmond is a man in a hurry, who has to seize every opportunity to make an impact before being closed down by the logic of the parliamentary arithmetic in Holyrood. He needs to move as fast as possible because a moving target is always harder for the opposition to hit.

"I was determined not to end up like Donald Dewar, that was constantly in my mind." But his real role model comes as a surprise, to me at least. "I'm a great fan of Harold Wilson, you know." Harold Wilson a political inspiration? The Gannex-wearing pipe-smoker who became the butt of 1960s cartoonists? It's not as daft as it sounds: Wilson achieved a lot in two years, with a minority administration, and then won a comfortable majority in 1966.

Wilson was a brilliant political improviser also. Somehow, I think Salmond will be in power long enough to get a decent diary out of it at least.