Anderson rozpoczął swoją karierę w zespołach juniorskich Grêmio. W 2004 roku został włączony do kadry pierwszego zespołu, jednak dwa lata później odszedł do portugalskiego FC Porto. 5 marca 2006 roku zadebiutował w barwach klubu podczas wygranego 3:0 spotkania ligowego z Nacionalem. Na koniec sezonu mógł wraz z zespołem cieszyć się z mistrzostwa Portugalii oraz Taça de Portugal. W październiku 2006 roku złamał nogę, co wyłączyło go z gry na długi czas, ostatecznie jednak ponownie zajął wraz z Porto pierwsze miejsce w lidze. 30 maja 2007 roku Anderson został zawodnikiem Manchesteru United, który zapłacił za niego 17 milionów funtów. Z nową drużyną czterokrotnie zdobył mistrzostwo Anglii oraz szereg innych trofeów. Na początku 2014 roku został wypożyczony do Fiorentiny. 2 lutego 2015 roku Manchester United rozwiązał kontrakt z zawodnikiem. 3 lutego 2015 roku został oficjalnie zaprezentowany jako piłkarz SC Internacional. W 2019 roku zakończył karierę.