Partite a eliminazione diretta con gare di andata e ritorno. In caso di pareggio nei tempi regolamentari, passa la squadra che ha realizzato il maggior numero di gol fuori casa. Nel caso non sia possibile determinare un vincitore con la regola dei gol fuori casa, sono previsti i tiri di rigore.
Nei primi due turni (primo turno e sedicesimi di finale) se la squadra che gioca la prima partita in trasferta vince con 2 o più gol di scarto, è automaticamente qualificata al turno successivo senza dover disputare la gara di ritorno.
Partecipanti
10 squadre ammesse tramite Ranking CBF, 54 tramite piazzamenti nelle competizioni statali.
^(PT) Ranking da CBF (01/12/2003), su www1.folha.uol.com.br, folha.uol.com.br, 2 febbraio 2004. URL consultato il 16 ottobre 2009.
^abcdefghijkPartita di ritorno non disputata in quanto la squadra in trasferta ha vinto l'andata con 2 o più reti di scarto e si è quindi qualificata automaticamente al turno successivo.
^Il Gama schierò un giocatore non disponibile nella partita di andata e inizialmente fu assegnato il passaggio del turno a tavolino al Paranavaí. Una sentenza successiva del 12 marzo 2004 riammise invece il Gama ai sedicesimi di finale.
^Partita non disputata in quanto tutti i giocatori del Barra do Garças nella partita di andata non potevano essere convocati, passaggio del turno a tavolino in favore del Santa Cruz.