Leaders are gathering in Vilnius for the NATO summit this week, and one topic that won't be on the agenda is the appointment of a new chief to succeed Stoltenberg at the end of the year.
That's because the Norwegian's tenure has been extended by another year for the second time, despite him previously announcing his intention to leave.
The next NATO chief is now likely to be appointed in 2024, when elections within the union will trigger a reshuffle of key EU posts.
This could further complicate the political balancing act of appointing a successor.
Many European leaders are said to be in line for the role, including EU Commission President Ursula von der Leyen. But conflicting political interests and personal preferences mean the choice of NATO's next chief will test the Alliance's capacity for compromise.
A politically charged decision
The role of NATO chief is determined through informal diplomatic discussions between member states and has historically been held by a European, while the military chief, the Supreme Allied Commander in Europe, has always been an American.
As the war on European soil continues, the role carries significant political weight and responsibility.
"The search for a new secretary general is not a competitive process, it is a political process," according to Bruno Lété, senior fellow at the German Marshall Fund.
"A number of interests from the member states must be taken into account. And member states are fighting each other in the diplomatic corridors to put their preferences for candidates on the front stage.”
"His [Stoltenberg's] extended tenure probably tells us that NATO was not united internally on who could become the next secretary general. And this rift is something to worry about,” he added.
French President Emmanuel Macron is said to be reluctant to accept a non-EU candidate.
Washington Seal of Approval
While the role is decided by consensus, Washington's approval is essential. Each nominee must be approved by the President of the United States.
Put forward by Prime Minister Rishi Sunak, British Defense Secretary Ben Wallace's candidacy was reportedly blocked by President Biden after the UK announced plans to train Ukrainian pilots in US-made F-16 jets without consulting the US.
Recent reports suggest that Biden favors European Commission President Ursula von der Leyen. A former German defense minister, she would bring relevant experience and a track record of securing unanimous support for Ukraine.
Calm, cool, stable
Stoltenberg has raised the bar very high when it comes to cool leadership in times of crisis.
A former UN climate envoy and prime minister of Norway, he is a seasoned diplomat and seasoned mediator. During his youth, Stoltenberg was also an anti-war activist and admitted to throwing stones at the US Embassy in protest against the Vietnam War in the 1970s.
He has successfully held the alliance together during one of the biggest security threats in its history, despite differing views on the extent of alliance support for Ukraine.
"NATO needs a lot of his experience," says Lété.
Before the invasion of Ukraine, he also successfully dealt with rebellion within his alliance, from Donald Trump's threats to withdraw to Macron accusing the alliance of "brain death".
Stoltenberg must now carefully navigate resistance within his alliance to secure ratification of Sweden's accession.
While there will be no discussions on a potential successor at the Vilnius summit, leaders will undoubtedly be looking for a candidate who can support alliance unity during times of war.
Asked in February what advice he would give his successor, Stoltenberg replied: "To keep Europe and North America together."