Yisrael Beiteinu has its origins in the Israel of the late 1990s, when former Director-General of the Prime Minister's Office, Avigdor Lieberman was greatly disappointed by his former boss Benjamin Netanyahu and his negotiation with the Palestinian Authority. Netanyahu signed the Wye River Memorandum, which featured the division of the city of Hebron. This move was viewed by many right-wing Israelis, including many of Lieberman's own Russian-speaking community, as a betrayal of their values by Netanyahu. At the time of the Wye River Memorandum, the Russian-speaking community in Israel was mainly represented by the centre-right Yisrael BaAliyah, led by Natan Sharansky, who decided not to pull his party out of Netanyahu's coalition despite the division of Hebron, which further disappointed Lieberman and other right-wing Russian-speakers. This disappointment led to two Yisrael BaAliyah Knesset members, Michael Nudelman and Yuri Stern to break away from the party to form their own party Aliyah.
For the 1999 elections, Lieberman, Nudelman and Stern formed Yisrael Beiteinu, a party whose goal was to represent the right wing of the Russian-speaking community in Israel. The new party won four seats. Due to Ehud Barak's victory in the 1999 elections, the new party sat in the opposition in the new Knesset. On 1 February 2000, while sitting in the opposition, the party joined an alliance with the National Union, itself an alliance of mainly Religious Zionist right-wing parties led by Binyamin Elon, both parties remained fairly independent. The joint list joined Ariel Sharon's new unity government formed after the 2001 Israeli prime ministerial election. However, it attempted to quit the government just a few months later after Sharon's government gave another neighborhood of Hebron to the Palestinian authority. This move was delayed by Rehavam Ze'evi's assassination, but the joint-list, now led by Lieberman, left the coalition in 2002 anyway.
In the 2003 elections, the Lieberman-led joint list won seven seats, with his Yisrael Beiteinu being given four of them. The alliance joined Ariel Sharon's government and Lieberman was made Minister of Transport. However, the party left the government on 6 June 2004, in response to the disengagement plan. On 1 February 2006, shortly before the elections that year, the party split from National Union in order to run alone in the elections. The two parties believed that they would each increase their power if they ran alone, because Yisrael Beiteinu mainly targeted Israel's right-wing secular Russian-speaking community, while the National Union mainly targeted Israel's national-religious community.
During the election campaign, Yisrael Beiteinu split from mainstream right-wing policy by offering a new peace plan based upon land and population transfers, it became known as the Lieberman plan. The party's new outlook on security was bolstered by the recent addition to the party, former Shin Bet deputy-director Yisrael Hasson, who was notably not a member of the Russian speaking community, and represented an attempt to reach out to new demographics. The 2006 elections were a great success for Yisrael Beiteinu, which increased its power to 11 seats. Yisrael Beiteinu joined Ehud Olmert's governing coalition in October 2006. The party entered a controversy in January 2007 when it entered a dispute with its coalition partner the Labor Party over Labor nominating Raleb Majadele for the position of Minister of Science and Technology, thereby making him Israel's first Muslim Arab minister. Lieberman condemned the nomination, and called for the Labor party's head, Amir Peretz's resignation, accusing him of harming Israel's security by ceding to "internal rivalries" within the Labor party, while Peretz accused Yisrael Beiteinu of being a racist party. Yisrael Beiteinu's member of Knesset (MK) Esterina Tartman referred to Peretz's decision as a "lethal blow to Zionism", adding that Majadale's presence in the cabinet would damage "Israel's character as a Jewish state" and that "We need to destroy this affliction from within ourselves. God-willing, God will come to our help." Tartman's comments were immediately condemned as racist by other MKs.
In January 2008 the party left the government in protest against talks with the Palestinian National Authority, saying certain issues negotiated were not to be tolerated. Lieberman pulled out of the government and left his position as Minister of Strategic Affairs, and almost immediately afterwards, Arutz Sheva reported that an investigation against Lieberman and his daughter that had been "ongoing for years, suddenly became active again once he left the government last week".
On 22 December 2008, Lieberman approved the party's list for the 2009 elections. In these elections, Yisrael Beiteinu continued to try and reach out to new demographics. As part of this attempt, the party added Orly Levy (daughter of former Likud MK David Levy, a figure highly respected by Israel's Mizrahi community) and Likud minister Uzi Landau to its list. Yisrael Beiteinu ran a highly controversial election campaign, featuring the slogans: "No citizenship without loyalty" and "Only Lieberman understands Arabic", these slogans were considered racist by many Israelis. These moves were a great success for Yisraeli Beiteinu, and polling showed that the party could win as many as 21 seats in the Knesset. In the end, Yisrael Beiteinu won 15 seats in the Knesset, making it the third-largest party after Kadima (28) and Likud (27), this was the party's best election result in its history. In March 2009, Yisrael Beiteinu joined Benjamin Netanyahu's coalition, and party leader Avigdor Lieberman became Deputy Prime Minister and Foreign Affairs Minister, while the party received four other ministerial portfolios, and one deputy minister post.
On 25 October 2012, Lieberman and Prime Minister Benjamin Netanyahu announced that Yisrael Beiteinu and Likud would run together on a single ballot in Israel's 22 January 2013 general elections known as Likud Yisrael Beiteinu. "In view of the challenges we're facing, we need responsibility on a national level ... We're providing a true alternative, and an opportunity for the citizens to stabilize leadership and government", Lieberman said.
The joint list was not very successful in the 2013 elections, as the combined power of the two parties went down from 42 seats to 31 seats. Despite the fall in strength, the joint list was still able to lead Israel's new government, and Yisrael Beiteinu retained most of its strength by holding 13 seats in the joint list. Lieberman was reappointed as Netanyahu's foreign minister. The alliance was officially dissolved on 9 July 2014, and the two parties did not run together in the next elections. On 24 December, Yisrael Beiteinu was hit by a major corruption scandal, which greatly hurt the party's image in the public eye and its standing in the polls.
The 2015 elections were a disaster for Yisraeli Beitenu, as the party went down to just 6 Knesset Members, losing over half its strength in the Knesset. Many of the party's former Knesset Members, such as Faina Kirschenbaum were implicated in the corruption scandal that hit the party, and therefore Lieberman had to reshuffle his list and bring forth many new people, such as the journalist Sharon Gal. Despite supporting the formation of a government by Netanyahu, Lieberman chose to keep his party in the opposition, due to personal disputes with Netanyahu and ideological disputes with the ultra-Orthodox parties such as Shas and United Torah Judaism. On the 26th of May 2016, Yisrael Beiteinu joined Netanyahu's coalition, Lieberman himself was appointed as Minister of Defense . The party's Knesset Member, Orly Levy left the party over the entry into the coalition and sat as an independent Knesset Member until the next elections, where she went on to found the Gesher party.
On 14 November 2018, Lieberman announced his resignation from the Israeli government, in protest to a new Gaza ceasefire,. On November 16, 2018, Netanyahu stated that he would name himself the new Defense Minister. As a result of Lieberman's departure, Yisrael Beiteinu also quit Netanyahu's coalition government. Lieberman's resignation was completed on November 18, 2018. The narrow government that followed Yisrael Beiteinu's departure led to Netanyahu calling a new election.
In the resulting 2019 elections, Yisrael Beiteinu ran a campaign focused on branding itself as a party for the "Secular Right", and focused on the issue of conscripting ultra-Orthodox Jews while simultaneously supporting aggressive security policy against Palestinian terrorism. During the election period, polling showed that Yisrael Beiteinu was at risk of falling below the electoral threshold required to enter the Knesset for the first time in its history, however, despite these polls, the party managed to get 5 seats in the new Knesset, giving it the ability to decide if Netanyahu formed a right-wing government. The government formation in 2019 was somewhat of a repeat of the situation in the previous elections, Yisrael Beiteinu supported Netanyahu to form a government, but refused to join it, citing an ideological dispute with the ultra-Orthodox parties over the ultra-Orthodox draft law as the reason for remaining in the opposition. Lieberman's refusal to join Netanyahu's coalition led to new elections being called.
On the 15th of June 2019, ahead of the September 2019 elections, Lieberman announced that Yisrael Beiteinu would only support a national-unity government composed of Likud and the centrist Blue and White and devoid of ultra-Orthodox parties. In an interview with Israel's Channel 13, Lieberman said: "We will aim for a government with Likud and with Kahol Lavan, and that will be an emergency government, a national-liberal government...We will do everything to limit the Haredim, so that they won't enter the government"