Foi das grandes apostas vitorianas no projecto de reformulação que o Vitória levou a cabo naquela época de 1999/2000. Proveniente do Benfica, Nandinho foi das figuras de proa desse ano, ao voar na ala direita, criando desequilíbrios, realizando assistências... em suma uma aposta que parecia ter tudo para dar certo nos Conquistadores.
Porém, no exercício subsequente, fruto da partida do treinador Quinito, em litígio com Pimenta Machado no final do ano antecedente, chegaria um novo treinador que era um regresso sebastiânico ao Vitória: Paulo Autuori. Imediatamente dispensou dois jogadores importantes do exercício anterior que eram Tito que partiu para Alverca e Nandinho. Como este reconheceu em entrevista ao Expresso de 14 de Novembro de 2020, "Quando lá chegámos disseram-nos que íamos ser dispensados e ficámos a treinar à parte. Assim, sem nenhuma explicação. O treinador tinha trazido quatro ou cinco brasileiros com ele e não sei se na altura também não tinha vindo algum jogador que estava emprestado..."
Sem arranjar clube, ficaria a treinar à parte, sem poder sair do Vitória, pois o Benfica, o seu anterior clube, pagava-lhe metade do contrato, sendo que se saísse de Guimarães essa cláusula seria revogada, ficando o novo clube na obrigação de pagar ao jogador a totalidade do seu salário.
Porém, em Outubro desse ano haveria de ser reintegrado, atento ao facto de Autuori ter sido despedido, ainda que o novo treinador Álvaro Magalhães poucas oportunidades lhe tivesse dado. Seria, pois, com o terceiro técnico desse ano, Augusto Inácio, que iria começar a ter uma utilização mais efectiva, ainda que numa nova posição no terreno que era a de lateral direito por iniciativa daquele. Com efeito, "Quando o Inácio chega perguntou-me se podia jogar a lateral direito, se já tinha jogado nessa posição, disse-lhe que sim, e joguei a lateral direito até ao final da época. Nos últimos jogos é que já joguei a extremo. Foi uma época em que estivemos a lutar até à última jornada para não descer."
Não obstante ter recuperado relevância na equipa, haveria de selar o seu destino na penúltima jornada desse sofrido campeonato, quando o Vitória se deslocou à Madeira para defrontar o Marítimo., onde o jogador foi titular, não obstante ter estado doente durante toda a semana. No momento em que a equipa insular marcou o único tento de desafio, à passagem dos 36 minutos, seria substituído por Fangueiro.
Zangado com o sucedido, "Quando eu ia a sair os jornalistas para os directos das televisões perguntam-me porque é que eu tinha saído e eu, ingénuo, disse: "Olhe, não sei, pergunte ao treinador porque eu também não percebi". Ele ficou chateado com a situação e apesar de eu me ter retratado no balneário, de ter pedido desculpa pela minha reacção a quente e de pensar que as coisas estavam sanadas, a verdade é que…" teria a sentença ditada.
Deste modo, no início da época seguinte com uma proposta para sair para a Grécia, confrontou o treinador Inácio se contava com ele, numa indagação que o treinador rechaçou para o presidente que confirmou o interesse no jogador. Porém, "uma semana antes de começar o campeonato, uma pessoa minha conhecida que conhecia o treinador, ligou-me e disse: "Tem cuidado porque eu acho que estão a preparar-se para te dispensar." De imediato, ligou a Pimenta Machado que disse "Não, isso é tudo mentira, nem pensar".
Apesar disso, no primeiro dia de trabalhos, ao apresentar-se no clube, "quando estou a fazer exames médicos chega o director, entrega-me uma carta que dizia estava dispensado e para procurar clube." Indignado, “quis logo falar com o treinador, ele não quis falar comigo, fugiu. Acabei por ir falar com o presidente para perceber o porquê e ele disse-me que tinha sido por causa da situação da época anterior, por causa daquilo que se tinha passado.” Assim, "quis logo falar com o treinador, ele não quis falar comigo, fugiu. Acabei por ir falar com o presidente para perceber o porquê e ele disse-me que tinha sido por causa da situaçãoda época anterior, por causa daquilo que se tinha passado."
Por isso, passaria a temporada de 2001/02 a treinar sozinho, à espera que o seu contrato findasse, para no ano seguinte comprometer-se com o Gil Vicente...com a plena noção que poderia ter feito muito mais de Rei ao peito!