A época de 1995/96 começara cheia de esperança...e de ambição!
Depois da partida de Quinito, Pimenta Machado apostou na contratação de Vítor Oliveira, na altura um jovem treinador ao serviço do Gil Vicente, mas, acima de tudo na aquisição de jogadores de créditos firmados como Vítor Paneira e Neno (em litígio com Artur Jorge, no Benfica). Além disso, contrabalançou as vendas dos "Pedros" ao Sporting com as entradas Capucho, Edinho e Ramires como moeda de troca. Promoveu-se, ainda, o regresso de Soeiro, que houvera actuado no Marítimo, contratando-se ainda o médio defensivo Marco Freitas e o central brasileiro Arley Alvarez. Era um conjunto que permitia sonhar.
Porém, desde cedo se percebeu que Vítor Oliveira não tinha capacidades para conduzir a equipa. Demasiado defensivo e com dificuldades em lidar com as estrelas, sentiu dificuldades em levar o barco a bom porto, ainda que tenha conseguido nas provas europeias eliminar o Standard Liége e, durante 45 minutos, em Camp Nou, dar um banho de bola à equipa liderada por Johann Cruyff e que contava com nomes como Figo, Kodro, de La Peña... e não fosse o árbitro gaulês, Alain Sars, a surpresa poderia durar mais tempo!
Não obstante isso, no campeonato o Vitória era uma sombra do que se esperava. Titubeante, sem chama e com o treinador a incompatibilizar-se com os principais jogadores, a época ameaçava terminar sob o signo da desilusão. Até que Pimenta Machado resolveu agir. Após uma dolorosa derrota em Leça, graças a um golo do icónico Constantino, que gerou uma acesa contestação ao treinador, não hesitou: despediu Oliveira, que, ainda disse num programa televisivo que os clientes da Cervejaria Martins deveriam ser entrevistados em vez dele, em alusão à tradicional discussão futebolística que ocorre no popular snack-bar vimaranense.
Depois de cinco jogos em que Manuel Machado assumiu o comando interino da equipa, Pimenta Machado tomou uma decisão ousada. Estávamos no início de 1996, e o país abria a boca de espanto com a (quase) proeza da equipa da União de Lamas que quase eliminara o campeão nacional, FC Porto, em plenas Antas, tendo desperdiçado uma grande penalidade no derradeiro minuto da partida. A orientá-la estava um antigo internacional português, Jaime Pacheco. Seria esse o escolhido.
Com ele, o Vitória ganhou nova vida, novo élan. Estreando-se a vencer em Faro, com um golo no derradeiro minuto de Dane, ainda foi travado na jornada seguinte, em casa, pelo Benfica, numa noite em que a exibição infeliz do guardião Neno na segunda parte ditou uma dolorosa derrota.
Porém, a partir daí, tudo mudou. A equipa passaria a apresentar um futebol entusiasmante, de profundo pendor ofensivo, ainda que o treinador assumisse " que quando não podemos tocar violinos, tocamos bombos." Tal levou a que o Vitória lavrasse dois ciclos de seis triunfos consecutivos, entrecortados com um empate a zero na Amadora. Durante esta caminhada, destaque para o triunfo em Alvalade por três bolas a duas, depois de ao intervalo estar a perder por dois tentos sem resposta e no FC Porto, já campeão nacional, por igual resultado.
A duas jornadas do final o sonho passava pela conquista do terceiro lugar, numa prova sublime. Não haveria de suceder, com a equipa a escorregar em casa frente ao Boavista, para ir jogar a Braga, sem a motivação, dos grandes momentos que tinha vivido, naquele que foi o último jogo da carreira de N'Dinga.
Contudo, estava garantido mais um apuramento europeu e uma história para a posteridade: campeões da segunda volta com um futebol trepidante e entusiasmante!