L'archéologie n'a pas suffisamment expliqué la préhistoire de la Guinée-Bissau. En 1000 avant JC, il y avait des chasseurs-cueilleurs dans la région, des centaines de milliers d'années après avoir traversé le reste de l'Afrique. Cela a été bientôt suivi dans les archives archéologiques par des agriculteurs utilisant des outils en fer.

​

La Guinée-Bissau faisait autrefois partie du royaume de Gabu, qui faisait partie de l'empire du Mali au XVIe siècle. Certaines parties de ce royaume ont persisté jusqu'au 18ème siècle. D'autres zones du territoire qui composent actuellement le pays étaient considérées par les Portugais comme faisant partie de leur empire.

La Guinée-Bissau était connue sous le nom de Côte des esclaves, car c'était une zone importante pour l'exportation d'esclaves africains par les Européens à destination de l'hémisphère occidental.

​

Les premiers récits d'Européens arrivés dans cette région incluent ceux du voyage du Vénitien Alvise Cadamosto en 1455, du voyage en 1479-1480 du marchand franco-flamand Eustache de la Fosse et de Diogo Cão. Dans les années 1480, cet explorateur portugais atteint le fleuve Congo et les terres de Bakongo, jetant les bases de l'Angola moderne, à quelque 4200 km au large des côtes africaines de la Guinée-Bissau.

​

Bien que les rivières et la côte de cette région aient été parmi les premiers lieux colonisés par les Portugais, qui ont créé des comptoirs commerciaux au XVIe siècle, ils n'ont exploré l'intérieur qu'au XIXe siècle. Les dirigeants africains locaux en Guinée, dont certains ont grandement prospéré grâce à la traite des esclaves, contrôlaient le commerce intérieur et n'autorisaient pas les Européens à entrer dans la région. Les communautés africaines combattant les marchands d'esclaves se méfiaient également des aventuriers européens et des futurs colons. Les Portugais en Guinée étaient en grande partie limités aux ports de Bissau et de Cacheu. Un petit nombre de colons européens ont établi des fermes isolées le long des rivières intérieures de Bissau.

​Pendant une brève période dans les années 1790, les Britanniques tentèrent d'établir une base rivale sur l'île de Bolama. Cependant, au XIXe siècle, les Portugais étaient suffisamment en sécurité à Bissau pour considérer également la côte voisine comme leur territoire, il en va de même au nord dans une zone appartenant actuellement au Sénégal.

​Une rébellion armée, déclenchée en 1956, par le Parti Africain pour l'Indépendance de la Guinée et du Cap-Vert (PAIGC) sous la direction d'Amílcar Cabral a progressivement consolidé son autorité sur ce qui était alors la Guinée portugaise.  Contrairement aux mouvements de guérilla dans d'autres colonies portugaises, le PAIGC a rapidement étendu son contrôle militaire sur de grandes parties du territoire, aidé par le terrain semblable à la jungle, son approche facile de la frontière avec les alliés voisins, et par de grandes quantités d'armes provenant de Cuba, de la Chine, de l'Union soviétique et des pays africains de gauche. Cuba a également accepté de fournir des experts en artillerie, des médecins et des techniciens. Le PAIGC a même réussi à se doter d'une importante capacité anti-aérienne pour se défendre contre les attaques aériennes. En 1973, le PAIGC contrôlait de nombreuses régions de Guinée, bien que le mouvement ait subi un revers en janvier 1973, lorsque Cabral a été assassiné.

​

L'indépendance a été déclarée unilatéralement le 24 septembre 1973, qui est maintenant célébrée comme le jour de l'indépendance du pays, un jour férié. La reconnaissance est devenue universelle après le 25 avril 1974, le coup d'État militaire d'inspiration socialiste au Portugal, qui a renversé l'Estado Novo à Lisbonne. Nicolae Ceaușescu de Roumanie, a été le premier à reconnaître officiellement la Guinée-Bissau et le premier à signer des accords avec le Parti africain pour l'indépendance de la Guinée et du Cap-Vert.