Charlie Hebdo published a special edition on Wednesday to mark the Arab Spring, renaming the weekly newspaper Charia (Sharia) Hebdo for the occasion and featuring a front-page cartoon of the prophet saying: "100 lashes if you don't die of laughter!"
The newspaper's website also appeared to have been hacked on Wednesday, with its regular home page replaced with a photo of the Grand Mosque in Mecca and a message reading: "No god but Allah".
French officials were quick to denounce the attack and offer support to the newspaper.
"Freedom of expression is an inalienable right in our democracy and all attacks on the freedom of the press must be condemned with the greatest firmness. No cause can justify such an act of violence," Prime Minister Francois Fillon said in a statement.
Fillon said he had asked Interior Minister Claude Gueant to ensure "all light is shed on the origin of this fire and that its perpetrators be prosecuted."
At the scene, Gueant told journalists: "Of course everything will be done to find the perpetrators of this attack, and this must certainly be called an attack."
Police said the fire at the newspaper's offices started around 1am. No one was injured in the blaze, which a police source said was suspected to have been caused by a petrol bomb.
The magazine's publisher, known only as Charb, said he was convinced the fire was linked to the special edition.
"On Twitter, on Facebook, we received several letters of protest, threats, insults," which had been forwarded to the police, he said.
"Our problem now is to be able to put a paper out next Wednesday," he said.
"There is soot everywhere, the computers are in my opinion dead, the electrical system is melted."
"This is the first time we have been physically attacked, but we won't let it get to us."
In a statement, the newspaper's editorial department said it was "against all religious fundamentalism but not against practising Muslims."
"We are for the Arab Spring, against the winter of fanatics," it said.
The weekly had said it would publish a special edition to "celebrate" the Ennahda Islamist party's election victory in Tunisia and the transitional Libyan executive's announcement that Islamic Sharia law would be the country's main source of law.
It would feature the prophet Muhammad as guest "editor", the magazine said.
As well as the cover cartoon, a back-page drawing featured Muhammad wearing a red nose and accompanied by the words: "Yes, Islam is compatible with humour."
The depiction of the prophet's face is strictly prohibited in Islam.
Charb on Tuesday rejected accusations that he was trying to provoke.
"We feel we're just doing our job as usual. The only difference is that this week, Muhammad is on the cover and that's quite rare," he told AFP.
A Paris court in 2007 threw out a suit brought by two Muslim organisations against Charlie Hebdo for reprinting cartoons of Muhammad that had appeared in a Danish newspaper, sparking angry protests by Muslims worldwide.
Pieces of paper and computers were strewn outside the newspaper's offices in eastern Paris after the fire, an AFP reporter said, and windows and glass doors were broken at street level and on the first floor.
The head of the French Council of the Muslim Faith, Mohammed Moussaoui, condemned the attack.
"If this was a criminal fire, we firmly condemn it," he told AFP.
Paris Mayor Bertrand Delanoe said he was "disgusted" with the attack.
"I want to condemn in the strongest possible terms this act of violence that is also an act of violence against freedom of expression," he told RMC radio.
"We can disagree with Charlie Hebdo's edition today but we are in a society that needs freedom of expression," Delanoe said.
The managing editor of left-leaning newspaper Liberation, Nicolas Demorand, said in a Tweet that his newspaper was inviting Charlie Hebdo's writers to work in Liberation's offices until they could find a new home.