Having started his career at Goiás of Goiânia, Fernandão had a four-year spell in France, initially moving to Marseille for R$1.4 million, before returning to Brazil to play for Internacional. He helped the club finish as runners-up in the 2005 season of the Campeonato Brasileiro Série A. In the same year, he had his first cap against Guatemala and made an assist for forward Fred to score a goal.
2006 was arguably Fernandão's best year. He led Sport Club Internacional to win the Copa Libertadores for the first time ever. Fernandão was a joint top scorer of the competition and was voted man of the Match in the final against São Paulo, match in which he scored one goal and made one assist. After the win, he extended his contract with Sport Club Internacional and skippered the club to win the FIFA Club World Cup in December. In May 2010 the same Brazilian club São Paulo FC announced the signing of striker Fernandão of Goiás for an undisclosed fee. In May 2011 the two sides agreed to terminate the playing contract between them in a friendly manner.