W latach 1963–1974 PAIGC prowadziła wojnę partyzancką z Portugalią. Vieira odgrywał w trakcie jej trwania kluczową rolę. Zyskał sobie pseudonim wojenny Nino. W 1964 został dowódcą frontu południowego. Od 1965 do 1967 był wiceprzewodniczącym Rady Wojennej PAIGC. Następnie delegatem Biura Politycznego na froncie południowym (1967-1970). W 1973 został zastępcą sekretarza generalnego PAIGC. We wrześniu 1973 PAIGC ogłosił niepodległość nowego państwa Gwinei Bissau, która we wrześniu 1974 została uznana przez Portugalię. Pierwszym prezydentem został brat zamordowanego Amilcara Cabrala, Luís Cabral. W latach 1973–1978 Vieira pełnił funkcję przewodniczącego Ludowego Zgromadzenia Narodowego. Od 28 września 1978 do 14 listopada 1980 był premierem Gwinei Bissau.

Zamach stanu i objęcie władzy Młode państwo od początku swego istnienia znajdowało się w trudnej sytuacji gospodarczej. Pozbawione surowców, było najbardziej zacofaną kolonią portugalską w Afryce, co wzbudzało nastroje antyrządowe. Dodatkowo w szeregach PAIGC dochodziło do konfliktów między Gwinejczykami z kontynentu a Kabowerdyjczykami z wysp, stanowiącymi elitę polityczną.