The party was formed as Parti KeADILan Nasional by Wan Azizah Wan Ismail, wife of former deputy prime minister Anwar Ibrahim, whose sacking and subsequent arrest in September 1998 shocked the nation. The party was at the forefront of the Reformasi movement to reform Malaysian politics and a founding member of the Barisan Alternatif alliance.
Between September 27 and 30, 1999, 7 of Keadilan's leaders, including vice-president Tian Chua, were arrested and prevented from standing for election. Coupled with a political miscalculation by allying too closely with the Islamic Party of Malaysia, scaring off non-Muslim voters, Keadilan won only 5 seats in the November 1999 general elections.
On April 10, 2001, the Keadilan leaders were again arrested under the Internal Security Act.
In February 2003, Keadilan merged with Parti Rakyat Malaysia (People's Party Malaysia) and adopted its current name.
See also: List of political parties in Malaysia, Politics of Malaysia