Under his leadership, improving relations with Russia will be NATO's second top priority, after resolving the situation Afghanistan, Rasmussen said:

“I believe that during my term as NATO Secretary General we should develop a true strategic partnership with Russia. We should extend practical co-operation in areas where we share security interests. There is clearly scope for us to work together on counter-terrorism, on Afghanistan, on piracy, on non-proliferation, and many other areas as well.”

He said he hoped the disputes and differences that the alliance and Russia have between them will not “poison” their relationship. NATO expansion is one of the major sticking points.

Moscow believes that the alliance’s expansion into Ukraine and Georgia could seriously destabilize the situation on the European continent. Earlier, Russia’s Deputy Foreign Minister said that NATO’s policy of support for Tbilisi had provoked Georgia’s aggression in the Caucasus in August 2008. Supporting Kiev’s membership bid is also leading to instability in the country, since the majority of its population is against joining NATO.

Russia’s envoy to NATO Dmitry Rogozin said, “I believe it’s important to hear NATO say that they’ve ceased pocketing whatever they see lay in temptation’s way”.

“Like they think Ukraine is there to pocket, to make a forced political sex change operation on Ukraine,” he is quoted as saying by Interfax.

Rasmussen reiterated the statement made by his predecessor Jaap de Hoop Scheffer, saying that he didn’t see Georgia and Ukraine as ready to become NATO members at the moment. He said, however, that the alliance will continue to support their membership bid, as was promised at the summit in Brussels in 2008.

Some experts say Rasmussen’s promises echo those by previous NATO leaders – ones that no one has ever kept.

“I don’t think that NATO and Russia have ever been doing different things. The problem is that they always look eye to eye, but haven’t managed to find a lot in common in their visions of the most crucial European security problems,” said Timofey Bordachyov, from the European Studies Centre at the Higher School of Economics.

“As I remember, every new Secretary General started his term by saying that he wants to revitalize relations with Russia, and none has ever brought too many benefits to both partners,” he said.

Meanwhile Afghanistan remains the alliance’s largest challenge. As Danish Prime Minister, Rasmussen strongly supported the US-led war on terror, contributing troops to NATO’s Afghan mission.

Now, while Barack Obama has increased the American military effort there, Europe is reluctant to match this boost. And as France has returned into the NATO military command structure after 40 years of being absent, analysts say the new chief will be walking a tight rope between Washington and its European allies.

“Some of our European friends, mainly France in NATO, expected that with the departure of George W. Bush they could increase their influence in NATO and privatize this institution, making it more European-oriented. And of course, the new Secretary General, as a pro-American politician, is a big disappointment for them,” Bordachyov said.

Konstantin Kosachev, the Head of the Foreign Affairs Committee of the Russian State Duma said that he believes that Rasmussen won’t place the disagreements with Russia in the foreground.

“At this stage Rasmussen demonstrates serious intention to unite rather than divide Europe on the outer borders of NATO,” he said in an interview with ITAR-TASS.

Russia’s envoy to NATO Dmitry Rogozin said the new NATO chief will possibly visit Moscow in autumn this year. He added that Rasmussen would be most welcome, but “we would like the new Secretary General to bring something positive here rather than just new requests over Afghanistan and so on”.

“Our generous Russian soul is ready to help, but it can’t last forever. We can’t be paying in advance all the time, we also want to get something in exchange,” Rogozin is quoted as saying by Interfax.

Speaking on the future of NATO, Rasmussen announced he has gathered a 12-strong panel of experts, chaired by former-US Secretary of State Madeleine Albright, to work on a new strategic development plan. He also called on the public to submit their views on the policies of NATO through the organization’s website.

Anders Rasmussen, 56, has become the 12th Secretary General in NATO’s 60-year history.

Read also Major global scandals make infamous Danish politician NATO chief