PAIGC won the most seats in the March 2004 parliamentary election, and Gomes became Prime Minister in May.
Το PAIGC κέρδισε τις πιο πολλές έδρες στις βουλευτικές εκλογές του 2004 και ο Γκόμες έγινε πρωθυπουργός το Μάιο.