La lutte armée débute le 23 janvier 1963, d’abord dans le sud du pays par des actions coordonnées, puis rapidement dans le nord. A noter que les combats se dérouleront exclusivement sur le territoire guinéen, le Cap-Vert ne sera jamais un théâtre d’opération.
Cabral et le PAIGC font preuve d’un pragmatisme révolutionnaire en s'appuyant sur les luttes passées (Chine, Cuba, et même les maquis de la Seconde guerre mondiale) et présente (Vietnam). D’essence marxiste et organisé selon les principes léninistes, le PAIGC ne commet pas l’erreur de l'adaptation systématique des schémas de guérilla comme certains mouvements latino-américains. Si les œuvres théoriques de Guevara La guerre de guérilla et de Debray Révolution dans la révolution sont connues, Amilcar Cabral rejette pourtant le foquisme et ne surestime pas le spontanéisme révolutionnaire des paysans. Il lui préfère une organisation révolutionnaire et une cohérence idéologique, basée sur un patient travail politique, selon le modèle chinois des années 1930 théorisé par Mao. Le marxisme-léninisme fournit certes un cadre d’organisation et de réflexion, mais à la lumière de la situation guinéenne. En effet les cadres du PAIGC s’appuient sur une connaissance concrète de la réalité du pays pour établir les principes tactiques et stratégiques de la lutte de libération. Le recensement de 1953 a fourni les bases de la stratégie révolutionnaire du PAIG, riches des considérations géographiques, historiques, économiques, sociales et culturelles de la Guinée et du Cap-Vert. La fine analyse des structures ethniques et leur potentiel révolutionnaire s’intègre à cette réflexion.
Dans un premier temps des groupes autonomes de combattants sont créés, tous reliés à la direction du PAIGC. Toutefois face aux tendances à l'isolement de certains chefs locaux, le parti instaure une direction collective de la guérilla, sous le contrôle du comité du parti. On assiste ainsi à une fusion totale du parti et des forces armées. Cette réorganisation est décidée lors du Ier congrès du parti tenu en février 1964. Le PAIGC se dote à cette occasion de nouvelles structures, avec un bureau politique de vingt membres, un comité exécutif de soixante-cinq membres divisé en sept départements (plus tard réduits à cinq) chargés de l’action militaire, des affaires extérieures, du contrôle politique des forces armées et de l’appareil du parti, de la sécurité, de l’économie et des finances et du développement de l’organisation du parti au sein de la population. Cabral, en tant que secrétaire général du parti, préside également le conseil de guerre, émanation du bureau politique.
Sur les modèles chinois et vietnamien, le PAIGC constitue des forces régulières, les Forces armées populaires du peuple ou FARP. A l’échelon local, des milices populaires articulées sur les Forces armées locales assure la défense des zones libérées. Les unités de combats des FARP sont bien structurées et très flexibles, capables de se disperser aussi rapidement qu’elles se sont réunies. A partir de 1964, le commandement est assuré conjointement entre un officier et un commissaire politique. Le soutien en matériel (armements, équipements divers) provient surtout de l’extérieur, de Libye, d’Algérie, d’Union soviétique et des pays de l’est, de Chine populaire et de Cuba, mais aussi des pays scandinaves qui fournissent des produits de première nécessité. La Guinée de Sékou Touré et le Sénégal offrent des bases logistiques. Enfin la diaspora guinéenne joue également un grand rôle dans le soutien au PAIGC.
Les FARP ont recours à des actions classiques de guérilla contre les Portugais, coups de mains, attaques de postes, embuscades, mais aussi des opérations plus ambitieuses. Elles poussent les Portugais à refluer vers les zones urbaines, à se terrer dans des places fortifiées, les maintiennent sous pression.
Cette situation met en lumière la contradiction même de la stratégie portugaise : pour contrôler la population les militaires portugais doivent se disperser, mais ce faisant ils s'affaiblissent et s'exposent à des attaques les obligeant à se concentrer. En se concentrant ils abandonnent du terrain au PAIGC. Ces zones délaissées sont investies par les guérilleros, « travaillées » politiquement et ainsi perdues par le colonisateur. En 1968, le PAIGC contrôle ainsi les deux tiers du pays. Dans un de ses textes, Cabral peut affirmer avec justesse que « la lutte armée s'est plus intégrée à la population que la population ne s'est intégrée à la lutte armée », validant les mots de Mao selon qui le guérillero doit être comme un poisson dans l’eau.
