The flames - which are believed to have started at around 18h - have now been completely extinguished, according to the emergency services on the scene.
Currently, it is thought that the fire started accidentally, as a result of the €6m building and restoration work that had been taking place on-site.
A police inquiry has been opened into a case of “involuntary destruction by fire”, with work beginning as the flames died down on Monday night.
The main structure of the cathedral, along with both towers, were saved, along with the major pieces of art contained inside. However, two thirds of the roof was damaged and collapsed, along with the famous spire.
Jean-Claude Gallet, brigade commander for the Paris firefighters, said: “We can consider that the structure of Notre-Dame has been saved and preserved in the main.”
Reconstruction work could “take decades”, according to the director of cathedral association la Fondation de l'Œuvre Notre-Dame.
A statement said: “What will determine this, is the diverse sources of documentation, and copies that will allow the architects and businesses to reconstruct it to its former state."
Notre-Dame spokesperson, André Finot, said: “The minister for culture made significant investments on the fire security a few years ago. [Fire alarms were installed] everywhere, along with 24 hour personnel to avoid any fire starting.”
This allowed the building to be evacuated completely within “two to three minutes”, he said - although it did not help stop the flames at that time.
Culture minister Franck Riester said: “We know that is it not criminal, and it seems that the fire started in a place where there was scaffolding. Scaffolding that was in place with an aim to restore the spire.”
He acknowledged “the extraordinary courage” of the firefighters that were on the scene as the flames broke out, but said it is “too early” to be sure of the exact time reconstruction will take. He estimated that it could “take months, years”.
Firefighters deliberately isolated the famous towers as part of their work, reports said, to avoid them from being affected.
At 23h30 last night, the curate general of the diocese of Paris “was able to enter the cathedral”. He said: “Everything was black, burned; it smelled very strongly.”
Monseigneur Philippe Marsset said: “The miracle is in the firefighters. If God protected the Cathedral, it was through their genius work. They intervened very quickly. The two belfry towers were saved by the firefighters who flooded the two towers to stop the bells and their supports from falling.
“If one tower had fallen, the other one would have too, and the façade that we see today would have be on the ground.”
President Emmanuel Macron last night cancelled plans to address the nation on the subject of the recent Grand Débat, and said: “[I feel the] emotion of all the nation. Thoughts for all Catholics and for all of the French people. Like all of us, I am sad tonight to see this part of us burning.”
Mr Macron visited the scene, along with other figures including Ms Hidalgo and Prime Minister Edouard Philippe.
He said: “The worst was avoided, even if the battle is still not entirely won. The next hours will be difficult.”
This morning, he said: “We will rebuild. All of us together. This is part of our French destiny. I am involved - from tomorrow (April 16) a national fund will be launched.”
Heritage group La Fondation du Patrimoine has now opened a national fund in the wake of the disaster, to help raise money for the reconstruction of the iconic building.
Already, fashion giant LVMH and the Arnault family have pledged €200 million, while the Pinault family have promised €100 million.
The Ile-de-France region will spend €10 million on emergency repair work, it has said, while Paris mayor Anne Hidalgo has announced a €50 million contribution from the city of Paris itself.
Ms Hidalgo said: “I do not have words strong enough to express the pain that I feel in front of Notre-Dame ravaged by flames...all Parisians and French people are lamenting this emblem of our common history. As we do, we will find the strength to get back up.”
She added the Latin motto of the city of Paris: “Fluctuat nec mergitur”, which translates roughly as “rocked by waves but does not sink”.
But art historians and heritage experts have condemned the incident, saying that there had been a lack of care towards the historic monument in the run up to the disaster.
Didier Rykner, editor-in-chief of the art magazine Tribune de l’Art, said that safety during works on historic buildings was always “notoriously poor”.
He said: “We could have avoided this. It is one fire too many. Rules around works on historic monuments are insufficient. I demanded a law on it, and nothing happened. Those responsible will have to be pinpointed...What happened isn’t normal.”
Historian Jean-Michel Leniaud has said: “What happened was inevitable. The lack of real maintenance and daily attention on this major building is the cause of this catastrophe. It is not about finding who is responsible; the responsibility is shared, because this is the most collective monument in the country.”
Art historian Alexandre Gady described his emotions as an “immense sadness” and “a sort of cold anger”, and said that “the budget of historic buildings has been too low for years”.
He said: “We are going to spend billions on the Olympic Games in 2024, which are going to ruin us, but before this fire, we did not have enough money to maintain the cathedral? I cannot hide a certain anger.
“We are not going to reconstruct Notre-Dame, we are going to repair it. But we did lose it. I said to myself, that to see such a building, in a city like Paris, in a country that is the sixth-most powerful in the world...there is a deep disappointment in feeling so helpless in the face of what happened.
“This is the image of France, this is our history. We have put it in danger.”
The disaster comes just days after 16 historic copper statues - representing 12 apostles and four evangelists - were removed as part of the wider restoration work.
Notre-Dame is one of France’s most popular tourist attractions, with an estimated 13 million visitors per year.
