The dramatic vote, less than two months after parliamentary elections, marked a setback for Netanyahu and sent the longtime leader's future into turmoil.
Netanyahu, who has led Israel for the past decade, had appeared to capture a fourth consecutive term in the April 9 election. But infighting among his allies, and disagreements over proposed bills to protect Netanyahu from prosecution stymied his efforts to put together a majority coalition.
Rather than concede that task to one of his rivals, Netanyahu's Likud party advanced a bill to dissolve parliament and send the country to the polls for a second time this year.
"I didn't spare any effort to avoid unnecessary elections," Netanyahu said after the vote, lashing out at an ally-turned-rival, Avigdor Lieberman, who refused the prime minister's offers to join the government.
He said the country was being forced to hold "unnecessary, wasteful elections because the people had their say. They didn't have their say enough for what Mr. Lieberman wants."
Had the deadline passed without the vote, Israel's president would have given another lawmaker, most likely opposition leader Benny Gantz, an opportunity to put together a coalition.
After the vote, Gantz angrily accused Netanyahu of choosing self-preservation over allowing the country's political process to run its course.
Gantz said that Netanyahu opted for "three crazy months" of a new campaign and millions of wasted dollars over new elections because he is "legally incapacitated" by looming indictments. "There is no other reason," Gantz said.
The country now plunges into a new election campaign that will last at least three months under Israeli law. With much of the country on vacation in late August, a tentative date of Sept. 17 was set.
The campaign looks to complicate Netanyahu's precarious legal standing. Israel's attorney general has recommended pressing criminal charges against him in three separate corruption cases, pending a hearing scheduled for October.
Even if Netanyahu wins the election, it is unlikely he will be able to form a government and lock down the required political support for an immunity deal before an expected indictment. That would force him to stand trial and put heavy pressure on him to step aside.
The political uncertainty could also spell trouble for the White House's Mideast peace efforts. The U.S. has scheduled a conference next month in Bahrain to unveil what it says is the first phase of its peace plan, an initiative aimed at drawing investment into the Palestinian territories.
With the Palestinians, who accuse the U.S. of being unfairly biased toward Israel, opposed to the plan, and Netanyahu preoccupied with re-election, it remains unclear how the Americans will be able to proceed. President Donald Trump's top Mideast adviser, son-in-law Jared Kushner, was in Israel and scheduled to meet with Netanyahu on Thursday.
That Netanyahu struggled to secure a majority coalition in the 120-seat parliament was a shocking turn of events for the country's dominating political figure.
In the April 9 vote, Likud and its hardline nationalist and religious parties captured a majority of 65 seats.
The immediate cause of the crisis was his dispute with Lieberman, a former aide who leads the small Yisrael Beitenu faction.
The men had clashed over Lieberman's demand to subject ultra-Orthodox religious males to the military draft, which is compulsory for most Jewish males. Without Lieberman's five Knesset seats, Netanyahu had no parliamentary majority.
But the deeper issue is connected to Netanyahu's legal troubles. Facing a likely indictment, he had pushed his coalition partners to pass legislation that would grant him immunity and curb the powers of the country's Supreme Court.
Opposition parties strongly oppose granting Netanyahu immunity, robbing him of any alternatives to Lieberman as he tried to form a coalition.
For the past two decades, Lieberman has alternated between being a close ally and a thorn in the side of his former boss. He has held a number of senior Cabinet posts, including defense minister and foreign minister.
Lieberman's base of support is fellow immigrants from the former Soviet Union, and he takes a hard line toward the Palestinians but also is staunchly secular.
He has demanded that the parliament pass pending legislation that requires young ultra-Orthodox men to be drafted into the military. Years of wide exemptions for religious men have generated resentment among the rest of Jewish Israelis, who are required to serve.
"I am not against the ultra-Orthodox community. I am for the state of Israel. I am for a Jewish state but against a Halachic state," Lieberman wrote on Facebook early Wednesday, using a term that refers to a Jewish state governed by Jewish law.
The ultra-Orthodox parties consider conscription a taboo, fearing that military service will lead to immersion in secularism, and insist the exemptions should stay in place. Netanyahu, dependent on the parties' political support, says they have compromised enough and refuses to press them further.
Netanyahu maintained contacts with Lieberman and other parties in hopes of forging a deal as a parliamentary debate took place. Many of the Likud speakers lashed out at Lieberman, accusing him of forcing an unnecessary election.
But as a parliamentary debate stretched toward midnight, it became clear there would be no compromise.
A bitter Netanyahu claimed after the vote that Lieberman "had no intention" to compromise and made unrealistic demands. "He is dragging the entire country for another half a year of elections," he said.