Vitória speelde in de jeugd van FC Alverca uit zijn geboortestad. Zijn debuut in het profvoetbal maakte hij echter voor Fanhões in de vierde divisie. Tussen 1990 en 1999 speelde hij voor União Desportiva Vilafranquense, waarmee hij vier seizoenen in de derde divisie uitkwam. Later kwam hij in de vierde divisie ook nog uit voor Seixal, Casa Pia en Alcochetense.
Zijn trainersloopbaan bracht Vitória langs grotere clubs. Hij begon nog bij Vilafranquense, waar hij zelf nog als speler actief was. Hierna was hij tussen 2004 en 2006 jeugdtrainer bij de grootmacht SL Benfica. Bij CD Fátima begon hij aan zijn eerste grote trainersklus. Met de club werd hij het seizoen 2008/09 kampioen van de Segunda Divisão. Na vier jaar tekende hij een contract bij FC Paços de Ferreira. Na een jaar vertrok hij naar Vitória de Guimarães waarmee hij in seizoen 2012/13 de Taça de Portugal won, tegen Benfica. Op 15 juni 2015 werd bekend dat Vitória de nieuwe hoofdtrainer van SL Benfica werd, nadat Jorge Jesus de opvallende en pikante overstap maakte naar stadsgenoot Sporting Lissabon. Met Benfica won Vitória in zijn eerste seizoen ondanks een matige start het landskampioenschap en de Taça da Liga, het tweede bekertoernooi van Portugal, en bereikte hij de kwartfinales van de Champions League, waarin FC Bayern München te sterk bleek. Hij werd dat seizoen coach van het jaar in Portugal. Het seizoen erop won Vitória de Portugese supercup, de Taça de Portugal en opnieuw het landskampioenschap. In 2018/19 werd Benfica opnieuw landskampioen. Tussendoor had Vitória een 43 jaar oud record verbroken door 16 uitwedstrijden in de Primeira Liga te winnen. Op 4 januari 2019 werd hij na een reeks matige resultaten ontslagen bij Benfica. Een week later werd Vitória hoofdtrainer bij het SaoedischeAl-Nassr. Met die club werd hij in zijn eerste halfjaar ook landskampioen en werd de supercup gewonnen. Op 27 december 2020 werd zijn contract met wederzijds goedkeuren ontbonden. In mei 2021 werd bekend dat Vitória de nieuwe trainer van Spartak Moskou werd. In juli 2022 volgde hij zijn landgenoot Carlos Queiroz op als bondscoach van Egypte.