Multi-party democracy was introduced to Guinea-Bissau by the ruling African Party for the Independence of Guinea and Cape Verde (PAIGC) in May 1991, and the PRS was established on 14 January 1992 by Kumba Ialá, a former PAIGC member.
Ialá was the party's presidential candidate in the 1994 general elections. He received 22% of the vote in the first round on 3 July, progressing to the run-off. Although the other opposition parties united behind him he lost to incumbent President João Bernardo Vieira by the narrow margin of 52%–48%. In the parliamentary elections the PRS won 10.3% of the vote and won 12 seats, emerging as the third-largest party in the National People's Assembly.
After Vieira was deposed on 7 May 1999, the transition government under Malam Bacai Sanhá arranged new elections. Ialá ran as the PRS candidate for president for a second time, emerging as the leading candidate in the first round. In the second round he defeated Sanhá by 72%–28%, becoming the country's first non-PAIGC president. The PRS also emerged as the largest party in the National People's Assembly, winning 38 of the 102 seats, whilst the PAIGC was also beaten by the Resistance of Guinea-Bissau-Bafatá Movement. The PRS nominated Caetano N'Tchama as Prime Minister in January 2000.
Ialá resigned as President of the PRS in May 2000, although he continued to play an influential role in the party. Prime Minister Alamara Nhassé was elected as party leader in January 2002 at a PRS convention. However, following his dismissal as Prime Minister later in the year, he resigned as party leader and was replaced by Alberto Nan Beia.
The PRS's time in power was characterized by a poor economic situation and political instability. Ialá, alleged by critics to be erratic and to have autocratic tendencies, dissolved parliament in November 2002, but early elections intended to be held in February 2003 were delayed several times, until Ialá was ousted in a coup led by Veríssimo Correia Seabra on 14 September 2003. Seabra's military government chose the PRS's general secretary Artur Sanhá to become Prime Minister of a transitional government, with Henrique Rosa as President; they were sworn in on 28 September. Sanhá took office despite the opposition of 15 of the 17 involved political parties, which said that the Prime Minister should be an independent.