Paulo Bento chegou ao Vitória na temporada de 1991/92.
Revelado no Estrela da Amadora, desde logo afirmou-se no esquema gizado por João Alves, ganhando durante três temporadas, o estatuto de indiscutível no papel de médio defensivo dos conjuntos vitorianos.
Seria assim, como dissemos, com Alves, continuaria na segunda curta passagem de Marinho Peres pelo Castelo e teria confirmação durante a temporada e meia em que Bernardino Pedroto liderou o Vitória, salvando-o, inicialmente da despromoção, para na temporada seguinte falhar o apuramento europeu... também, por causa, de duas grandes penalidades falhadas pelo jogador que dessa marca houvera retirado o record de inviolabilidade a Vítor Baía, num empate a um contra os portistas.
Pelos bons atributos apresentados, no final da temporada 1993/94, o canto da sereia proveniente do Benfica seduziu o jogador. A ele e ao lateral esquerdo, Dimas. Com efeito, Artur Jorge, que chegava coberto de fama e fortuna do estrangeiro, pretendia contar com ambos os jogadores para reformular a equipa, contando para isso com os dois vitorianos.
Porém, passados poucos dias das contratações terem sido efectivadas, a bomba estourou. E de modo altissonante.
Assim, depois do jogador ter chegado a Lisboa, as prestações relativas ao seu pagamento foram suspensas, com fundamento que este se encontrava lesionado com uma pubalgia.
Tal gerou a indignação nas hostes vitorianas, principalmente no presidente António Pimenta Machado, que de imediato garantiu que " “em virtude da postura pouco lícita, pouco séria da direcção do Benfica, enquanto estes senhores estiverem à frente do clube, o Vitória não tem mais relações institucionais com eles."
Justificava tal decisão pelo facto de a 15 de Junho de 1994 ter sido acertada a transferência dos dois jogadores para Lisboa, sendo que, dois dias depois, Paulo Bento fez exames médicos no estádio da Luz. Dez dias depois, o Benfica enviou um conjunto de cheques pré-datados para Guimarães, vencendo-se o primeiro a dia 31. Todavia, antes dessa data, o Benfica deu ordens para o pagamento ser revogado. Para Pimenta "o Vitória poderá, eventualmente, ser vítima de guerrilhas entre dirigentes do Benfica que não tiveram protagonismo nesta transferência e que alguns consideraram talvez um pouco cara, mas seja o que for somos vítimas e não temos culpa alguma.”
Manuel Damásio, o presidente do Benfica, defendeu-se dizendo que tentaram chegar a um acordo, visto o jogador ter de ser operado, esperando que o pagamento fosse retomado após a operação.
Pimenta Machado, esse, deu ordens para o assunto ser resolvido nos tribunais, algo que não sucedeu, pois as partes acabaram por se entender e Paulo Bento recuperaria a tempo de efectuar 29 jogos pelo conjunto lisboeta nessa época, apenas menos cinco do que realizara na anterior no Vitória...