A decision to press formal charges against the veteran premier now rests with the attorney general's office, which is expected to take weeks or months to decide how to proceed.
Netanyahu, prime minister for nearly 12 years, addressed the nation as news of the recommendations broke, proclaiming his innocence and pledging to continue to lead the country.
"Over the years, I have been the subject of at least 15 enquiries and investigations," Netanyahu said in the televised address, standing before four Israeli flags and appearing tense.
Netanyahu to face new questioning over graft
"Some have ended with thunderous police recommendations like those of tonight. All of those attempts resulted in nothing, and this time again they will come to nothing."
A prime minister who is facing such police recommendations or who has been formally charged with offences is not obliged to resign.
Police said in a statement they were recommending his indictment on bribery, fraud and breach of public trust.
Police have been investigating Netanyahu over suspicions that he and his family received expensive gifts from Hollywood producer Arnon Milchan and Australian billionaire James Packer. The gifts allegedly included pricey cigars, jewellery, and champagne.
Netanyahu goes on offensive against 'fake news'
They have also been probing allegations Netanyahu sought a secret deal for favourable coverage with the publisher of top-selling newspaper Yediot Aharonot.
Police recommended indicting Milchan and the publisher, Arnon Moses, with bribery as well, the statement said.
"Those recommendations have no legal value in a democratic country," Netanyahu said in his address, referring to his own case.
He added that "our government will finish its term and I am sure that in the next elections (due in 2019), I will again win your confidence."
The 68-year-old right-wing premier has been questioned seven times by police over the allegations and has called the investigation an attempt by political opponents to force him from office.
Last week, Netanyahu lashed out at police in a rare attack as indications grew that detectives were preparing to recommend his indictment, questioning their ability to act fairly.
In Tuesday's recommendations, police said Netanyahu had been suspected of trying to help Milchan receive tax benefits in Israel, of assisting him in receiving a visa in the United States and of promoting his business interests.
Milchan, who is Israeli, has produced many films, including the blockbuster "Pretty Woman".
Police said they had questioned some 80 witnesses.
While an indictment alone would not legally oblige Netanyahu to resign, he would likely face mounting pressure to do so. He would be legally forced to step down if convicted and with all appeals exhausted.
He has already faced a series of large protests in Tel Aviv over the corruption cases.
Netanyahu wife faces possible graft trial: ministry
Parliament could also enact a special procedure against him before his case is exhausted if he is found to be guilty of moral turpitude.
Netanyahu's time as premier is fast approaching Israel's revered founding father David Ben-Gurion's 13 years, and he has shown himself to be a shrewd politician.
But an indictment is sure to encourage his political rivals — including those from within his own party — to move against him.
Israel has not shied away from pursuing criminal cases against top politicians.
Former prime minister Ehud Olmert resigned from office after police recommended he be indicted for graft. He was freed from prison in July after being granted parole from a 27-month sentence.
He has largely remained out of the public eye since his release, but Israeli media reported that he broke his silence on the Netanyahu case last week.
"I wish for the prime minister that he end his term quickly and in a seemly manner," Olmert, also known for his taste for fine cigars, was quoted as saying.
COMMENTS
Comments are moderated and generally will be posted if they are on-topic and not abusive.
For more information, please see our Comments FAQ