One of the assailants was captured on video outside the building shouting "Allahu Akbar!" (God is Greatest) as shots rang out. Another walked over to a police officer lying wounded on the street and shot him point-blank with an assault rifle, before the two calmly climbed into a black car and drove off.
A police union official said the assailants - Interior Minister Bernard Cazeneuve said there were three in total - remained at liberty and there were fears of further attacks. The official described the scene in the offices as carnage.
The government declared the highest state of alert, increasing security at transport hubs, religious sites, media offices and department stores as the search for the assailants got under way.
Charlie Hebdo (Charlie Weekly) is well known for courting controversy with satirical attacks on political and religious leaders of all faiths and has published numerous cartoons ridiculing the Prophet Mohammad. Jihadists online have repeatedly warned that the magazine would pay for its ridicule.
The last tweet on its account mocked Abu Bakr al-Baghdadi, the leader of the militant Islamic State, which has taken control of large swathes of Iraq and Syria and called for "lone wolf" attacks on French soil.
While there was no claim of responsibility, supporters of Islamic State and other jihadist groups hailed the attack on Internet sites, citing cartoons of Mohammad as the reason. Governments throughout Europe have expressed fear that fighters returning from Iraq or Syria could launch attacks in their home countries and may now review their own security.
President Francois Hollande, who will address the nation on television Wednesday evening, rushed to the scene of what appeared to be a carefully-planned attack. Sirens could be heard across the city.
"An act of indescribable barbarity has just been committed today in Paris," he said. "Measures have been taken to find those responsible, they will be hunted for as long as it takes to catch them and bring them to justice."
An amateur video broadcast by French television stations shows two hooded men all in black outside the building. One of them spots a wounded policeman lying on the ground, hurries over to him and shoots him dead at point-blank range with a rifle.
The two then walk over to a black saloon car. One casually picks up a shoe left on the ground, and then they drive off.
In another clip on Television station iTELE, the men are heard shouting in French: "We have killed Charlie Hebdo. We have avenged the Prophet Mohammad."
Paris prosecutor Francois Molins said the assailants killed a man at the entrance of the building to force entry. They then headed to the second floor and opened fire on an editorial meeting attended by eight journalists, a policeman tasked with protecting the magazine's editorial director and a guest.
"According to a witness who survived, they shouted Allahu Akbar and said they wanted to avenge the Prophet," Molins said.
A witness quoted by 20 Minutes daily newspaper said one of the assailants cried out before getting into his car: "Tell the media that it is al Qaeda in Yemen!"
Three firefights ensued, the first with a patrol car responding to initial emergency calls, the second with two policemen on bicycles and a third with another patrol car.
The gunmen fled eastwards by car toward the Paris suburbs. There they hit another car and were forced to abandon their vehicle in a residential area, Molins said.
They then hijacked another car before disappearing. He declined to give any details on the hunt for the shooters.
"There is a possibility of other attacks and other sites are being secured," police union official Rocco Contento said.
A Reuters reporter saw groups of armed policeman patrolling around the Grands Magasins department stores in the shopping district and there was an armed gendarme presence outside the Arc de Triomphe.
President Barack Obama described the attack as cowardly and evil.
"The fact that this was an attack on journalists, an attack on our free press, also underscores the degree to which these terrorists fear freedom of speech and freedom of the press," he told journalists in the White House.
Another 11 people were injured in the attack, including four critically.
Sources at the weekly said the dead included co-founder Jean "Cabu" Cabut and editor-in-chief Stephane "Charb" Charbonnier.
"Two black-hooded men entered the building with Kalashnikovs (rifles)," witness Benoit Bringer told TV station iTELE. "A few minutes later we heard lots of shots."
In a video shot by journalist Martin Boudot from a rooftop near the magazine's offices, a man can be heard screaming "Allah"; then followed the sound of three or four shots.
A firebomb attack gutted the headquarters of Charlie Hebdo in November 2011 after it put an image of the Prophet Mohammad on its cover in what it described as a Shariah edition.
France last year reinforced its anti-terrorism laws and was already on alert after calls from Islamist militants to attack its citizens and interests in reprisal for French military strikes on Islamist strongholds in the Middle East and Africa.
The imam of Drancy mosque in Paris's Seine-Saint-Denis northern suburb, Hassen Chalghoumi, condemned the attack.
"I am extremely angry. These are criminals, barbarians. They have sold their soul to hell. This is not freedom. This is not Islam and I hope the French will come out united at the end of this," he said.
Dozens of police and emergency services were at the site as police secured a wide perimeter around the shooting site, where a Reuters reporter saw a police car riddled with bullet holes.
German Chancellor Angela Merkel was among European leaders condemning the shooting.
"This abominable act is not only an attack on the lives of French citizens... It is also an attack on freedom of speech and the press, core elements of our free democratic culture."
Rico, a friend of Cabut, who joined thousands in vigil at the Place de la Republique in Paris, said his friend had paid for people misunderstanding his humor.
"These attacks are only going to get worse. It's like a tsunami, it won't stop and what's happening today will probably feed the (far-right) National Front," he told Reuters.
The National Front has won support on discontent over immigration to France. Some fear Wednesday's attack could be used to feed anti-Islamic agitation.
Germany's new anti-immigration movement said the attack highlighted the threat of Islamist violence. Merkel has condemned the PEGIDA movement, which drew a record crowd of 18,000 to its latest rally on Monday in Dresden.
The last major attack in Paris was in the mid-1990s when the Algerian Armed Islamic Group (GIA) carried out a spate of attacks, including the bombing of a commuter train in 1995 which killed eight people and injured 150.