According to the paper, Italy's Foreign Minister Franco Frattini is now no longer in the running, and was never in fact a serious candidate, making it near certain that there will be a consensus behind appointing Stoltenberg at a key meeting on Friday.
The newspaper said that it expected the appointment to be announced when Nato country foreign ministers meet in Brussels on Tuesday and Wednesday next week.
According to the paper, Stoltenberg's candidacy was already unopposed when Nato ambassadors from the 28 members country's met ínformally on Thursday last week.
Stoltenberg on Tuesday made his first public comments on Nato's most pressing issue -- Russia's annexation of the Ukraine -- since his candidacy was first reported on Sunday.
Story continues below…
"Russia's use of military force to change borders is unacceptable," he said in the Norwegian parliament. "It is very serious that we see. For the first time after the war, a European government has forcibly changed boundaries and annexed part of a neighbouring country," he said.