Die PAICV, die sich selbst als Afrika-orientierte politische Partei sieht, im Gegensatz zu der etwas neoliberalen Partei Movimento para a Democracia (MpD), erfreut sich der größten Unterstützung in dem afrikanischen Festland vergleichbaren Bezirken: in dicht besiedelten städtischen Gegenden wie Praia und in landwirtschaftlich geprägten Arealen wie Santa Cruz (Kap Verde) und São Filipe.
1956 wurde ihre Vorgängerin, die Partido Africano da Independência da Guiné e Cabo VerdePAIGC (dt. Afrikanische Partei für die Unabhängigkeit von Guinea und Kap Verde), durch den kapverdischen nationalistischen Führer Amílcar Cabral gegründet. Die PAIGC kämpfte für die Überwindung des portugiesischen Kolonialreichs, für die Vereinigung von Kap Verde und Guinea-Bissau und benutzte ihre Kader, um die sozialistischeRevolution zu erreichen.
Seit 1961 kämpfte die PAIGC in einem Guerillakrieg in Zusammenarbeit mit ihren Schwesterparteien aus der CONCP-Gruppe (Conferência das Organizacões Nacionalistas das Colónias Portuguesas) im Portugiesischen Kolonialkrieg. Seit 1973 kontrollierte die PAIGC Guinea-Bissau; nach der Nelkenrevolution von 1974 wurde Kap Verde im Jahr 1975 unabhängig.
Nach den nationalen Unabhängigkeitskriegen etablierte die PAIGC einen sozialistischen Staat mit beiden Territorien unter Amílcar Cabrals Halbbruder Luís Cabral. Nach einem Militärputsch 1980 in Guinea-Bissau, der Cabral absetzte, spaltete sich Kap Verde ab und „sein“ Teil der Partei nahm den heutigen Parteinamen an. Die PAICV hielt ihr Regime der Ein-Parteien-Herrschaft und eines Staatssozialismus aufrecht bis zum Fall der Sowjetunion im Jahr 1991.
Bei den ersten Parlamentswahlen im Mehrparteiensystem wurde die PAICV 1991 von der konkurrierenden Partei MpD geschlagen.
Bei der Präsidentschaftswahl vom 11. und 25. Februar 2001 schlug Pedro Verona Rodrigues Pires, der im ersten Wahlgang 46,52 % der Stimmen erreicht hatte, seinen Kontrahenten von der MpD Carlos Veiga mit dem minimalen Vorsprung von 12 Stimmen.
