Stoltenberg said a report on the authorities' handling of the attacks "showed that a lot failed," and vowed Norway would aim to better ensure the public's safety.
He was addressing legislators called in from their summer break for an extraordinary session to discuss a scathing report on the authorities' lack of preparedness and bungled response to Breivik's July 22nd 2011 attacks.
Stoltenberg said an emergency preparedness centre would be opened in Oslo grouping together its SWAT team, helicopter unit and canine squads, in a bid to improve emergency responses.
He said authorities would also hold more emergency drills and exercises, improve the military's ability to assist police in emergencies, and improve security at sensitive locations.
An independent commission published a report on August 13th finding that the Oslo bombing of the government offices that killed eight people could have been prevented, and Breivik could have been arrested sooner on the island of Utøya where he spent more than an hour gunning down 69 people, mostly teens.
It concluded that political apathy led to the failure to implement a 2004 decision to cordon off the government block to traffic, and that the police's botched response to the shooting delayed Breivik's arrest.
"Grubbegata (the street outside the government block) should have been closed off, it wasn't. The killer could have been arrested earlier, he wasn't. Several security measures should have been implemented, they weren't," Stoltenberg acknowledged.
"I regret it," he said.
The failures brought to light by the report probably cost lives, the report suggested.
On the day of the massacre, the only police helicopter was out of action because its crew were on holiday, and a SWAT team took more than an hour to finally make it to the island, forced to use a pleasure boat after their inflatable almost sank.
Stoltenberg has come under fire since the report, undermining the huge popularity he enjoyed for his initial handling of the tragedy.
Tabloid Verdens Gang (VG), Norway's most widely-read paper, has called on Stoltenberg to resign.
But he has indirectly refused, saying it is his responsibility to ensure the commission's recommendations are implemented.
"I intend to do it," he said Tuesday.
With a year to go before Norway's next general elections, the right-wing opposition intends to keep up pressure on the government and may call a motion of no-confidence against the government.
That would however be purely symbolic as the centre-left coalition government holds a majority in parliament.
"It is serious that the authorities failed to protect the people," said opposition leader Siv Jensen of the right-wing populist Progress Party, the anti-immigration party of which Breivik was briefly a member.
Political scientist Bernt Aardal meanwhile told Norwegian news agency NTB that "the opposition now sees a possibility to hammer home criticism in the future: it's already accepted that this will mark the election campaign next year."
Breivik was last week found sane and sentenced to Norway's maximum sentence of 21 years in prison, to be extended indefinitely if he is still considered a threat to society.