In 2002, he signed with Ukrainian Premier League side FC Shakhtar Donetsk from Iraty Sport Club, going on to be an attacking mainstay over the course of the following seasons.

In a team filled with compatriots, Brandão scored a combined 39 goals in the three championships won by the club during that timeframe, notably topping the individual charts in the 2005–06 campaign at 15.

On 13 January 2009, Brandão left for France with Olympique de Marseille, netting eight times in 30 games in his first full season as they won the Ligue 1 trophy after an 18-year wait.

[2][3] In January 2012, Brandão returned to L'OM, notably scoring in the 92nd minute of a 2–2 away draw against Inter Milan in the campaign's UEFA Champions League round-of-16 second leg, enabling his team to advance on the away goals rule and reach the quarter-finals of the competition for the first time since 1993.

[5] Brandão was released in June 2012 along with Elinton Andrade, Djimi Traoré and Jean-Philippe Sabo and, two months later, signed with fellow league side AS Saint-Étienne on a two-year contract.