In the worst attack, a Paris city hall official said four gunmen systematically slaughtered at least 87 young people at a rock concert at the Bataclan concert hall before anti-terrorist commandos launched an assault on the building.
Dozens of survivors were rescued, and bodies were still being recovered on Saturday morning.
Some 40 more people were killed in five other attacks in the Paris region, the official said, including an apparent double suicide bombing outside the Stade de France national stadium, where Hollande and the German foreign minister were watching a friendly soccer international.
The assaults came as France, a founder member of the US-led coalition waging air strikes against Islamic State in Syria and Iraq, was on high alert for terrorist attacks.
It was the worst such attack in Europe since the Madrid train bombings of 2004, in which 191 died.
Hollande said the attacks had been organised from abroad by Islamic State "barbarians", with internal help.
Sources close to the investigation said a Syrian passport had been found near the body of one of the suicide bombers.
"Faced with war, the country must take appropriate action," Hollande said after an emergency meeting of security chiefs.
He also announced three days of national mourning.
Former president Nicolas Sarkozy added in a statement: "The war we must wage should be total."
During a visit to Vienna, US Secretary of State John Kerry said, "We are witnessing a kind of medieval and modern fascism at the same time."
In its claim of responsibility, Islamic State said the attacks were a response to France's campaign against its fighters.
It also distributed an undated video in which a militant said France would not live peacefully as long it took part in US-led bombing raids against them.
"As long as you keep bombing you will not live in peace. You will even fear travelling to the market," said a bearded Arabic-speaking militant, flanked by other fighters.
A French government source told Reuters there were 127 dead, 67 in critical condition and 116 wounded.
Six attackers blew themselves up and one was shot by police. There may have been an eighth attacker, but this was not confirmed.
The attacks, in which automatic weapons and explosives belts were used, lasted 40 minutes.
"The terrorists, the murderers, raked several cafe terraces with machine-gun fire before entering (the concert hall). There were many victims in terrible, atrocious conditions in several places," police prefect Michel Cadot told reporters.
State of emergency
After being whisked from the stadium near the blasts, Hollande declared a national state of emergency, the first since World War Two.
Border controls were temporarily re-imposed to stop the perpetrators from escaping.
Local sports events were suspended, department stores closed, the rock band U2 cancelled a concert, and schools, universities and municipal buildings were ordered to stay shut on Saturday. Some rail and air services were expected to run.
Sylvestre, a young man who was at the Stade de France when bombs went off there, said he was saved by his cellphone, which he was holding to his ear when debris hit it.
"This is the cell phone that took the hit, it's what saved me," he said. "Otherwise my head would have been blown to bits," he said, showing the phone with its screen smashed.
French newspapers spoke of "carnage" and "horror".
Le Figaro's headline said: "War in the heart of Paris" on a black background with a picture of people on stretchers.
Emergency services were mobilised, police leave was cancelled, 1,500 army reinforcements were drafted into the Paris region and hospitals recalled staff to cope with the casualties.
Radio stations warned Parisians to stay at home and urged residents to give shelter to anyone caught out in the street.
The deadliest attack was on the Bataclan, a popular concert venue where the Californian rock group Eagles of Death Metal was performing.
Some witnesses in the hall said they heard the gunmen shout Islamic chants and slogans condemning France's role in Syria.
The hall is near the former offices of the satirical weekly Charlie Hebdo.
France has been on high alert since Islamist gunmen attacked the paper and a kosher supermarket in January, killing 18 people.
Those attacks briefly united France in defence of freedom of speech, with a mass demonstration of more than a million people.
But that unity has since broken down, with far-right populist Marine Le Pen gaining on both mainstream parties by blaming immigration and Islam for France's security problems.
It was not clear what political impact the latest attacks would have less than a month before regional elections in which Le Pen's National Front is set to make further advances.
The governing Socialist Party and the National Front suspended their election campaigns.
US President Barack Obama and German Chancellor Angela Merkel led a global chorus of solidarity with France.
UN Secretary-General Ban Ki-moon condemned the "despicable attacks" while Pope Francis called the killings "inhuman".
France ordered increased security at its sites abroad. Italy, Russia, Belgium, Hungary and the Netherlands also tightened security measures.
Poland, meanwhile, said that the attacks meant it could not now take its share of migrants under a European Union plan. Many of the migrants currently flooding into Europe are refugees from Syria.
Julien Pearce, a journalist from Europe 1 radio, was inside the concert hall when the shooting began.
In an eyewitness report posted on the station's website, Pearce said several very young individuals, who were not wearing masks, entered the hall during the concert, armed with Kalashnikov assault rifles and started "blindly shooting at the crowd".
"There were bodies everywhere," he said.
The gunmen shot their victims in the back, finishing some off at point-blank range before reloading their guns and firing again, Pearce said, after escaping into the street by a stage door, carrying a wounded girl on his shoulder.
Toon, a 22-year-old messenger who lives near the Bataclan, was going into the concert hall with two friends at around 10:30pm (2130 GMT) when he saw three young men dressed in black and armed with machine guns. He stayed outside.
One of the gunmen began firing into the crowd. "People were falling like dominoes," he told Reuters.
He saw people shot in the leg, shoulder and back, with several lying on the floor, apparently dead.
Two explosions were heard near the Stade de France in the northern suburb of Saint-Denis, where the France-Germany soccer match was being played.
A witness said one of the detonations blew people into the air outside a McDonald's restaurant opposite the stadium.
In central Paris, shooting erupted in mid-evening outside a Cambodian restaurant in the capital's 10th district.
Eighteen people were killed when a gunman opened fire on Friday night diners sitting at outdoor terraces in the popular Charonne area nearby in the 11th district.
The prosecutor mentioned five locations in close proximity where shootings took place around the same time.