Mahajan's aspirations were always national, but he also did a significant amount of work in building up his party's fortunes in his home state of Maharashtra. In this, he was partnered with his childhood friend-turned brother-in-law Gopinath Munde (who is married to his sister Pradnya). Mahajan was responsible for his party's alliance with the Shiv Sena. The alliance went on to win the state assembly elections in 1995 and ruled till 1999. Munde was the deputy chief minister in that government.