The party was formed in 1995 following a split from the Communist Party of the Philippines due to ideological differences such as rejection of Maoism and preference for the act of insurrection over the Maoist protracted people's war.

The party, as well as its armed group Revolutionary Proletarian Army – Alex Boncayao Brigade, is known to be a "rejectionist" faction of the CPP-New People's Army due to its ideological differences from the latter, especially during the expulsion of 10,000 members from 1992 to 1993, the expulsion of former CPP member Rómulo Tabara, as well as the ex-secretary of the CPP's Metro Manila-Rizal Committee Filemón "Popoy" Lagmán.

These events during the "Second Great Rectification Movement" led by the CPP forced the faction to form a separate party in 1995.

Following ideological summits with the MR, CMR, Negros, Panay and Samar in October 1995, the protracted people's war was virtually rejected.

The Revolutionary Workers' Party - Mindanao (RPM-M) has been the Philippine section of the Fourth International since 2003.