miejsce w lidze, ale Nélsona chciały zatrudnić trzy najbardziej utytułowane kluby w kraju, SL Benfica, Sporting CP i FC Porto.
Benfica Nélson wybrał Benficę. Zaważył na tym fakt, iż zespół ten dopiero co wywalczył mistrzostwo kraju. Lizboński klub zapłacił Boaviscie sumę 1,5 miliona euro, a sam piłkarz podpisał pięcioletni kontrakt. Sezon 2005/2006 rozpoczął jako gracz pierwszej jedenastki. Osiągnął wysoką formę, co znalazło potwierdzenie zarówno w meczach ligowych, jak i Ligi Mistrzów. Miał duży udział w awansie Benfiki z fazy grupowej Ligi Mistrzów. To jego dośrodkowanie, po którym John O’Shea zdobył samobójczą bramkę, spowodowało, że Benfica po wygraniu 2:1 z Manchesterem United wyszła z grupy. Przed Bożym Narodzeniem doznał jednak kontuzji pachwiny i stracił miejsce w składzie na rzecz Brazylijczyka Alcidesa. W całym sezonie zagrał w 25 ligowych meczach i zdobył 1 gola. Benfica zajęła jednak dopiero 3. miejsce w lidze, przegrywając ze swoimi rywalami, Sportingiem i Porto. Od początku sezonu 2006/2007 Nélson jest znów podstawowym zawodnikiem Benfiki.