Þegar Portúgalar komu fyrst til eyjanna milli 1456-60, voru þær óbyggðar.  Árið 1460 sáu sæfararnir Diogo Gomes og António de Noli eyjarnar Maio og São Tiago og skírðu þær og tveimur árum síðar lentu fyrstu innflytjendurnir frá Portúgal á São Tiago og stofnuðu bæinn Tibeira Grande, sem óx og dafnaði sem miðstöð þrælasölu.  Hann varð fyrir árásum sjóræningja 1541 og Englendinga 1585 og 1592.  Eftir franska árás árið 1712 var bærinn loks yfirgefinn.  Blómaskeið eyjanna var fyrir bí, þegar dró úr þrælasölunni eftir 1876 og síendurteknir þurrkar og hungursneyð auk gerspilltrar stjórnar og óstjórnar bættu ekki úr skák.  Í lok 19. aldar batnaði ástandið nokkuð og skipaferðir um Atlantshafið milli Evrópu og Suður-Ameríku leiddu til opnunar kolahafnar og móttökustöðvar sækapals í Mindelo.  Í kjölfar fyrri heimsstyrjaldarinnar dró úr framförunum vegna færri skipaferða og þannig hélzt ástandið fram yfir síðari heimsstyrjöldina.

Árið 1951 var portúgalska nýlendar gerð að utanlandshéraði og tíu árum síðar fengu íbúarnir full borgararéttindi í Portúgal.  Þrátt fyrir þessa þróun, var sterk sjálfstæðishreyfing starfandi í landinu (Afríkski flokkurinn um sjálfstæði Gíneu-Bissau og Grænhöfðaeyja; PAIGC).  Gínea-Bissau á meginlandinu var einnig nýlenda Portúgala.  Árið 1975 urðu Grænhöfðaeyjar sjálfstætt lýðveldi með Aristides Pereira sem fyrsta forseta.  Árið 1981 sagði stærsti stjórnmálaflokkur eyjanna sig úr sambandi við PAICV og stofnaði PAICV, Sjálfstæðisflokk Grænhöfðaeyja.  Stjórnarskráin frá 1981 staðfesti sambandsslitin við Gíneu-Bissau.  Fyrstu þingkosningarnar samkvæmt stjórnarskránni frá 1992 fóru fram í desember 1995.  Í febrúar 1996 var Antonio Mascarenhas Monteiro kosinn forseti.