In 2007 Eduardo played for Grêmio on loan from RCD Espanyol. He is especially noted for being an extremely tight marker, and is booked with alarming regularity 
A member of Brazil's Under 17 World Cup winning side, he came to France in 2001 to play for FC Girondins de Bordeaux, where he commanded a regular first team spot for three seasons, including playing a key role of Bordeaux's Uefa Cup run in 2002–03. He followed that with a move to Olympique de Marseille, but after an unhappy year there, he was signed by Espanyol in 2005 for €4 million in 4-year contract. He did not play in 2008–09 Ligue 1, as he would occupied a non-EU quota. In January 2009 he left for São Paulo in 3-year contract.
On 8 August 2009 AS Monaco FC have signed the former São Paulo's Brazilian midfielder in 3-year deal.
On December 2010, Eduardo Costa was loaned to Vasco da Gama for 6 months. Six months after it became a permanent deal following Monaco's relegation from the Ligue 1.