PCM was formed in 1958 and its First Secretary was René Anselme Randrianja.
It held its first party congress in Antananarivo March 18-March 20, 1960.
Randrianja travelled to Moscow in 1960 to seek recognition, but was not invited to participate in the international conference of communist parties held there.
Afterwards he travelled to China, where he was received by the Chinese communists.
[1] The PCM published a forthnighly organ, Ady Farany in Malagasy language.