Kolone was first elected to parliament, the Legislative Assembly of Samoa, in 1967. In 1979, together with Tofilau Eti Alesana he founded the Human Rights Protection Party to oppose the government of Tupuola Efi. The HRPP won 24 seats in the 1982 election, and Kolone was appointed Prime Minister. However, an election petition stripped him of his seat shortly afterwards due to bribery charges and he was forced to resign.Tupuola Efi was appointed Prime Minister and served until Kolone regained his seat in the subsequent by-election. In the meantime Tofilau Eti Alesana had been elected leader of the HRPP and served as Prime Minister for the rest of the parliamentary term.
Kolone resigned from the HRPP after failing to regain the party leadership after the 1985 election. However in late 1985 11 HRPP Members of Parliament defected to form a coalition government with the then-opposition Christian Democratic Party. Kolone was elected Prime Minister on 30 December, with Efi as his deputy. The coalition was later formalised as the Samoan National Development Party. He subsequently led the SNDP in the 1991 election, gaining 14 seats.