Küba'da Cumhuriyet'in ilk dönemlerinden itibaren çok sayıda komünist ve anarşist örgüt vardı. Orijinal "uluslararasılaşmış" Küba Komünist Partisi 1920'lerde kuruldu. Parti 1944 yılında seçim nedeniyle Halkçı Sosyalist Parti olarak yeniden adlandırıldı. Temmuz 1961'de, Fulgencio Batista'nın başarılı bir şekilde devrilmesinden ve devrimci bir hükümetin kurulmasından iki yıl sonra, Entegre Devrimci Örgütler (ORI) kuruldu. Bu, şu örgütlerin birleşmesiydi:
- Fidel Castro'nun 26 Temmuz Hareketi
- Blas Roca liderliğindeki Popüler Sosyalist Parti
- Faure Chomón liderliğindeki öğrenci tabanlı Devrim Rehberi
26 Mart 1962'de ORI, Küba Sosyalist Devrimi Birleşik Partisi'ne (PURSC) dönüştü ve bu parti 3 Ekim 1965'te Küba Komünist Partisi adını aldı. 1976 tarihli Küba anayasasının 5. Maddesinde Komünist Parti "sosyalizmin inşası ve komünist topluma doğru ilerlemenin yüksek hedefleri doğrultusunda ortak çabaları örgütleyen ve yönlendiren, toplumun ve Devletin üstün yönlendirici gücü" olarak kabul edilmektedir. Komünist Parti de dahil olmak üzere tüm partilerin örgütlerinin reklamını yapmaları yasaklanmıştır.
Varlığının ilk on beş yılında Komünist Parti, Politbüro dışında neredeyse tamamen etkisizdi. Yüz kişilik Merkez Komitesi nadiren toplanıyordu ve ilk düzenli parti kongresi kuruluşundan on yıl sonra yapıldı. 1969 yılında partinin üye sayısı sadece 55,000'di (nüfusun %0.7'si) ve bu da PCC'yi dünyanın en küçük iktidardaki komünist partisi yapıyordu. 1975'teki ilk parti kongresine kadar parti iki yüz binin biraz üzerinde üyeye ulaşmıştı. Parti 1980 yılına gelindiğinde 430,000'in üzerinde üyeye ulaşmış ve 1985 yılına gelindiğinde 520,000'e yükselmiştir.