Pada awal 1960-an, Partai Afrika untuk Kemerdekaan Guinea dan Tanjung Verde (PAIGC) melancarkan perjuangan bersenjata melawan imperialisme Portugal yang akan berlangsung lebih dari satu dekade. Mendes adalah salah satu dari sedikit siswa Guinea-Bissau di pendidikan menengah ketika dia meninggalkan sekolah untuk bergabung dengan PAIGC. Ia naik pangkat pada tahun 1960-an, menjadi komisaris politik wilayah Bafatá pada tahun 1962. Pada tahun-tahun 1963–1964 ia memegang fungsi yang sama di Front Utara. Ia masuk Biro Politik pada tahun 1964 dan menjadi anggota Dewan Perang PAIGC pada tahun 1965. Pada tahun 1967 ia diangkat sebagai delegasi Dewan untuk Front Utara.[1][2]
