Estávamos na temporada de 2009/10. O Vitória, depois de ter percebido o erro que fora a contratação de Nelo Vingada, resolveu apostar em Paulo Sérgio, que se encontrava a trabalhar e a dar nas vistas em Paços de Ferreira.
Traria melhorias imediatas aos Conquistadores, estreando-se a 18 de Outubro de 2009, num triunfo por três bolas a uma frente ao Feirense, em partida a contar para a Taça de Portugal, graças aos golos de Desmarets, Douglas e de Nuno Assis.
Seria o início de uma escalada que fez com que a equipa conseguisse encostar-se ao quarto posto, então, ocupado pelo Sporting, até que de um momento para o outro a equipa encontrou um foco de instabilidade. Na verdade, depois dos Leões, que eram dirigidos por Carlos Carvalhal, terem visto fracassar a tentativa de contratarem o treinador que orientava a Académica de Coimbra, André Vilas-Boas para o exercício subsequente, viraram-se para o técnico vitoriano, acabando por contratá-lo por um valor na ordem dos 600 mil euros, apesar de poucos dias antes ter prorrogado o seu vínculo contratual com o Vitória por mais um ano, até 2011.
Deste modo, a partir desse momento, alguns factos começaram a minar a estabilidade vitoriana e a colocarem em causa o objectivo europeu que era o desejado e ambicionado. Nestes episódios, especial destaque para a conferência de imprensa que o, ainda, treinador vitoriano deu nas instalações do clube, em que ao lado do vice-presidente, Paulo Pereira, em vez de se dirigir aos vitorianos, como escreveu o Guimarães Digital de 20 de Abril de 2010 "... começou por falar para os sportinguistas, respondendo a quem possa ter dúvidas sobre a sua contratação. "Quero sossega-los porque a partir do primeiro dia que começar a trabalhar para o emblema do «leão, o objectivo é só um, ser campeão. Sei que este é o passo que tinha que dar para poder lutar pelos títulos." Só depois disso, haveria de dizer que "... "a cabeça do Paulo Sérgio está aqui, e só aqui, até 9 de Maio. Estamos empenhados em sairmos do Vitória com o clube nas competições europeias. É para isso que vamos lutar nas três jornadas que faltam."
Porém, não seria totalmente assim, ainda que o capitão vitoriano, Flávio Meireles, afiançasse que o técnico era um excelente profissional. Assim, antes do decisivo jogo com o Marítimo, referente à última jornada do campeonato e onde ao Vitória bastava um empate para se qualificar para as provas europeias, o Guimarães Digital de 04 de Maio de 2010, escrevia que "o ainda treinador do Vitória, Paulo Sérgio, esteve ontem reunido com Costinha, o Director Desportivo do Sporting. A notícia foi avançada ontem à noite pelo sítio do Mais Futebol. De acordo com aquele sítio, Paulo Sérgio aproveitou a folga em Guimarães para se deslocar a Lisboa, na companhia de um dos seus adjuntos. O encontro com Costinha e o novo director de comunicação do Sporting, Nuno Dias, terá acontecido numa localidade nos arredores de Lisboa."
O jogo acabaria por ser perdido, o Vitória falhar o apuramento europeu e Paulo Sérgio rumar sem glória para o Sporting, ainda que mal chegado a Alvalade, prometesse que "Venho para o Sporting procurar coisas grandes, e coisas grandes é vencer, é ser campeão, é lutar pelos títulos e dizê-lo isto de peito aberto porque é desta forma que eu quero o meu grupo de trabalho e a pensar em todos aqueles que nos rodeiam". Não acabaria a época, sendo despedido após a eliminação nos dezasseis avos da Liga Europa frente ao Glasgow Rangers... mas isso já seriam contas de um rosário que não o vitoriano.