For seven decades the powerful military coalition has been led by a series of western European men and now many observers expect the 30-strong group to choose a woman -- and perhaps a face from further east.

Stoltenberg is not expected to give up his seat until December, and still faces an enormous final challenge in guiding NATO through the crisis triggered by Russia's aggressive build-up of forces around the borders of beleaguered Ukraine.

But when the allies meet in Madrid at the end of June the national envoys represented on its North Atlantic Council are expected to have settled on a candidate, and speculation has already begun in Brussels -- home to NATO's headquarters -- on the names in the frame.

"The nomination process is opaque," a European diplomat told AFP, insisting on the anonymity that shrouds the closed-door and highly political hiring process. "No one campaigns openly, but many names circulate among the allies."

While the secretary general has always been a European -- just as the supreme allied military commander is always an American -- none of the hopefuls will reveal their interest until they are sure of the backing of US President Joe Biden's White House.

This reflects the reality that, while 21 of the 30 NATO members are also members of the European Union, the United States is still the unquestioned leader of the alliance.

This time round, however, many hope that the new civilian leader will at least come from an EU capital, as the West adjusts its power balance to accommodate what leaders like France's President Emmanuel Macron call "European sovereignty" or "strategic autonomy".

As the former NATO official said, "even the Americans" no longer oppose greater EU ambition.

- 'Credible candidate' -

So whose names are in the hat? Several emerge from conversations among officials and experts in Brussels, with the proviso that -- as with a Vatican conclave to choose a new pope -- the initial frontrunners often fall aside for a surprise finalist.

Former British prime minister Theresa May's name often comes up. She fits many of the criteria: a woman and a respected former head of government who hails from the country with NATO's second-biggest defence budget.

But, as a former senior NATO official confided, after Brexit a British leader might not be welcomed by some EU capitals and, in any case, Britain has already provided three of the previous 13 secretaries general and it might be the turn of one of the newer or smaller members.

The Brussels press is already speculating about an opening for Belgium's 47-year-old foreign minister Sophie Wilmes, who led a minority government as interim prime minister when the country struggled to tackle the early waves of the coronavirus pandemic.

For the senior diplomat, Wilmes is a "credible candidate ... who comes from an EU founding member, a good ally and partner, while her two predecessors were very reticent on European defence."

Some supporters of Stoltenberg, whose native Norway is not an EU member, admit that he was sometimes too dismissive of Europe's attempts to organise its own defence strategy within or alongside NATO, seeing a zero sum game in which any boost to European solidarity comes at the expense of the transatlantic alliance.

And his predecessor, Anders Fogh Rasmussen, came from Denmark, an EU member but with a defence establishment firmly enmeshed with US planning and a formal opt-out from EU common defence policy-making.

- New arrivals -

Wilmes would probably receive backing from France, which traditionally does not present a candidate of its own, but she did not wish to comment on the rumour, and ministers who have met her at recent EU councils told AFP she has not revealed any ambitions.

But, with Russia looming on the eastern horizon, many of the eastern member states -- who joined NATO after the West's victory in the Cold War saw the collapse of the Moscow-led Warsaw Pact -- no longer want to be seen as new arrivals, and will have candidates of their own.

Several names have surfaced, notably 65-year-old Dalia Grybauskaite, a former president of Lithuania and thus keenly aware of NATO's challenges on the Russian frontier but also a former European Union commissioner with friends in both of Brussels' major international bodies.

European officials were unanimous that it was time for a woman, and made the case for these three and several more -- citing former EU foreign policy chief the Italian politician Federica Mogherini, a friend of Stoltenberg who hosted him at the European School in Bruges to talk EU-NATO relations.

But one thing remains clear. "At the end of the day, it's Washington that decides," grumbled one European minister.