The party was formed in 1996 by Sharansky, whose personal image as a dedicated and long-suffering idealist was intended to be the catalyst for an immigrant revolution in Israeli politics. "Yisrael BaAliyah" was chosen as the name for the party, both denoting its identification with immigration, as well as the literal meaning of "Israel on the up". With another ex-Soviet dissident Yuli-Yoel Edelstein as a co-founder, they chose a slogan stating that their political party is different: its leaders first go to prison and only then go into politics. In its first electoral test, the May 1996 Knesset elections, the party won 5.7% of the vote and 7 seats, making it the sixth largest party in the Knesset. It joined Binyamin Netanyahu's Likud-led government, and was given two ministerial posts; Sharansky was appointed Minister of Industry and Trade, whilst Edelstein became Minister of Immigrant Absorption. On 23 February 1999, Shortly before the 1999 Knesset elections, Michael Nudelman and Yuri Stern left the party to form Aliyah, which later entered into an alliance with another Russian-immigrant party, Yisrael Beiteinu. In the elections, the party was reduced to six seats, but was now the fifth-largest in the Knesset, having campaigned on the popular motto "Ministry of Internal Affairs in our control". It joined Ehud Barak's One Israel-led government, and was given one ministerial portfolio and one deputy ministerial post. On 20 July 1999, shortly after the elections, left-wingers Roman Bronfman and Alexander Tzinker left the party and formed the Democratic Choice faction. Yisrael BaAliyah left the government on 11 July 2000, in response to suggestions that Barak's negiotations with the Palestinians would result in a division of Jerusalem. After Ariel Sharon won a special election for Prime Ministerin 2001, the party joined his new government, and was again given one ministerial post and one deputy position. In addition, Sharansky was appointed Deputy Prime Minister. In the January 2003 elections, the party was reduced to just two seats. Sharansky resigned from the Knesset, and was replaced by Edelstein. However, he remained party chairman, and decided to merge it into Likud. The merger went through on 10 March 2003, and Sharansky was appointed Minister of Jerusalem Affairs, whilst Solodkin was re-appointed Deputy Minister of Immigrant Absorption.
