His warning came after President Francois Hollande said he was willing to extend France's state of emergency for another six months following the Bastille Day massacre in Nice in which 84 people were killed.
"Even if these words are hard to say, it's my duty to do so: There will be other attacks and there will be other innocent people killed," Valls told French lawmakers.
Terror in France: Islamic State owns up to Nice truck attack
"We must not become accustomed to, but learn to live with, this threat," the prime minister added.
Valls also said suspected 'Islamist' Reda Kriket, arrested near Paris in March with an arsenal of weapons, had "surely" been planning to target the Euro 2016 football tournament in France, which wrapped up without an attack just over a week ago.
Hollande had only last Thursday announced a planned lifting of the emergency security measures -- which give the police extra powers to carry out searches and place people under house arrest -- originally imposed after the Paris attacks that killed 130 people last November.
French MPs will now mull a fourth extension of the eight-month-old state of emergency, as criticism mounts of the Socialist government's response to a slew of extremist attacks.
The Paris prosecutor's office said Tuesday that all the victims of the Nice massacre had finally been identified. Around 30 were Muslims, said an official from a regional representative body, and almost half were foreigners.
Five days after the attack, 70 people remain hospitalised, 19 in critical condition.
The remains of three Tunisians, including a four-year-old boy, killed in Nice were flown home on Tuesday.
Hollande, speaking during a visit to Portugal on Tuesday, urged the whole of Europe to make defence an absolute priority.
"We are up against challenges and that of terrorism is without doubt one of the largest ones," the French leader said.
France expected to extend emergency laws after Nice
With elections due next year, the political unity seen after the January 2015 attack on satirical magazine Charlie Hebdo has evaporated.
Valls was booed and heckled on Monday at a remembrance ceremony in Nice.
But the Socialists have said they will draw the line at some of the opposition's more controversial demands.
Republicans leader and former president Nicolas Sarkozy, eyeing another run for the top job next year, has called for anyone showing signs of being radicalised to be forced to wear an electronic tag, placed under house arrest or kept in a detention centre.
"We can't lock people up on the basis of mere suspicion, or suspicion of suspicion," minister for parliamentary relations Jean-Marie Le Guen retorted Tuesday.
Investigators say that 31-year-old Mohamed Lahouaiej Bouhlel, who used a 19-tonne truck to mow his victims down in Nice, had shown "recent interest" in extremist activity.
Authorities found "very violent" photos on his computer, of corpses, fighters posing with the IS flag and photos of al Qaeda founder Osama bin Laden.
However, Paris prosecutor Francois Molins said there was no direct evidence of the Tunisian's links to the Islamic State group (IS) -- which has claimed him as one of their "fighters."
Meanwhile a 35-year-old man, one of six people arrested and detained in connection with the Nice attack, was released late Tuesday, a judicial source said.
France calls on youth to join reserve forces after Nice attack
Among those still detained is a 38-year-old Albanian suspected of providing Bouhlel with a pistol he used to fire at the police who shot him dead.
The attack has hit tourism hard on the Cote d'Azur, where Nice -- France's second most-visited city after Paris -- is situated.
In Extenso tourism consultancy said hotel cancellation rates were running at 20-40 percent.
The aftershocks are being felt in the capital also, where the director of the luxury Plaza Athenee hotel told AFP the phone had been "ringing off the hook with cancellations for July, August and September".
Unlike the perpetrators of the Paris attacks, Bouhlel, a petty criminal with a history of violence and depression, did not travel to the Middle East for training or 'jihad'.
But he had a history of violence, with a doctor he consulted in Tunisia as a youth diagnosing psychotic tendencies.
In March, Bouhlel received a suspended sentence for armed assault after beating a driver with a nail-studded plank in an episode of road rage.
World reacts to Nice ‘terrorist’ attack
He showed no interest in religion until recently, Molins said, with acquaintances telling people he "ate pork, drank alcohol, took drugs and had an unbridled sexual activity".
But earlier this month, he stopped shaving his beard for what he dubbed "religious" purposes.
Interior Minister Bernard Cazeneuve says the government has bolstered security notably by sending thousands of troops into the streets.
But "there is no zero risk," he warned.
COMMENTS (1)
Comments are moderated and generally will be posted if they are on-topic and not abusive.
For more information, please see our Comments FAQ