Mosisili joined the Basotholand Congress Party of Ntsu Mokhele in 1967 and remained an active party member for the next 30 years. In 1993, he was elected to Parliament, representing his birthplace, Qacha's Nek. From 1993 until 1995 Mosisili held the minister of education portfolio. In February 1995 he was promoted to the post of deputy prime minister. Fearing a defeat in upcoming BCP elections, Mokhele led a mass walkout in 1995 and formed the Lesotho Congress for Democracy (LCD). A majority of the BCP Members of Parliament (MPs) followed Mokhele, including Mosisili, who was named deputy leader of the new political party. He became heir-apparent to the aging Mokhele and
held three ministerial portfolios (deputy prime minister, minister of home affairs, and minister of local government) from 1995 until 1998. When Prime Minister Mokhele announced his unexpected retirement from public life, the way was clear for Mosisili to assume leadership of the LCD. His party scored a landslide victory in elections held on 23 May 1998, winning 79 of 80 seats in Parliament. Mosisili was sworn in as the new prime minister.