Az arab-iszlám hatás a 7. században érte el az ország lakosait. A 8-13. században a nyugat-szudáni Ghána, a 13-14.században a Mali Birodalom része lett, a 15.században Szongáj fennhatósága alá került. Portugál hajósok már 1446-ban felfedezték a Zöld-foki szigeteket, a Gambia folyó torkolatát, valamint a part menti szigeteket. Az első portugál település Cacheau volt (alapítva 1588-ban), ezt Bissau (1600-ban) követte. Az ország 1879-ben lett Portugália gyarmata Portugál Guinea néven.

A vidék négy évszázadon át volt a rabszolga-kereskedelem központja. A 16-17.század során az angolok, franciák és hollandok is kereskedelmi telepeket hoztak létre. A 20.század kezdetétől a nagy monopóliumok zsákmányolták ki a gyarmatot. Elsősorban földimogyorót, pálmaolajat, rizst termesztettek, főként monokultúrában. 1942-ben Bolama helyett Bissau lett a főváros. Az ország 1951-től Portugália tengerentúli tartománya. A portugálok 1961-ben megszüntették az 1954-es "bennszülött statútumot", ami jelentős privilégiumokat biztosított a fekete afrikaiak egy vékony rétegének. Az ötvenes évek elejétől ellenállási csoportok működtek az országban s a Zöld-foki szigeteken. A csoportok 1956-ban a Partido Africano de Independencia de Guiné e Caco Verde (PAIGC), Guinea és a Zöld-foki szigetek Afrikai Függetlenségi Pártja szervezetében egyesültek. A PAIGC 1963-ban indított háborút Bissau-Guinea és a szintén portugál gyarmat Zöld-foki szigetek függetlenségének kivívásáért. Az Amilcar Cabral vezette felszabadító háború eredményeként 1972-ben tartották az első választásokat, s a népgyűlés kidolgozta a felszabadított Bissau-Guinea alkotmányát. Miután 1973 januárjában Cabralt Conakryban meggyilkolták, a népgyűlés 1973.szeptember 24-én egyoldalúan függetlenné nyilvánította az országot. Függetlenségét 1974 szeptemberében az 1974 áprilisában végrehajtott portugáliai államcsíny után létrejött új portugál vezetés hivatalosan is elismerte. Az ország első elnöke a meggyilkolt Amilcar Cabral öccse Luis de Almeida Cabral lett.