Nakon dvogodišnje epizode na mjestu sportskog direktora Dinama, Velimir Zajec se vraća u grčki Panathinaikos gdje je završio igračku karijeru. Osnovna zamisao bogatog vlasnika Vardinogiannisa bila je da preuzme mjesto šefa omladinske škole, no splet okolnosti ga u sezoni 1996./97. odvodi na trenersku klupu. U grčkoj sezoni Zajec se nije uspio plasirati u europska natjecanja, a u polufinalu Kupa je izgubio od Olympiakosa. No, signali iz Zagreba su bili sve češći, a u Zajecovom slučaju se poziv Dinama ne odbija.
Naslijedio Cicu
Zeko se vraća u rodni grad nakon što je Cico Kranjčar upisao dva poraza u Ligi prvaka. Kobna su za suigrača iz slavne ‘82. bila gostovanja kod Olympiakosa (2-0) i Porta (3-0). U kratkom vremenu Zajec hvata konce svlačionice i vodi Dinamo do pobjeda nad Ajaxom u Amsterdamu (1-0) i Portom u Zagrebu (3-1), dok je s Olympiakosom odigrao remi u Zagrebu (1-1). Smijenjen je 21. travnja 1999. nakon poraza protiv Rijeke (0-1), a koban je bio gol Boška Balabana.
Tri godine stagniranja od nogometa i novi zov Vardinogiannisa iz Atene odvodi Zajeca na mjesto sportskog direktora grčkog kluba. Tamo ga je pronašao srpski biznismen Milan Mandarić koji ga je pozvao da mu se pridruži u engleskom Portsmouthu.
Trener pa direktor
Nakon što se Mandarić razišao s Harryjem Redknappom, Zajec se u studenome 2004. spustio na klupu “mornara”. Uvodne pobjede protiv Boltona (1-0) i West Bromwicha (3-2) utišale su nezadovoljstvo navijača, a nakon pet mjeseci predao je dirigentsku palicu Alainu Perrinu. S mjesta direktora Portsmoutha Zajec je otišao u listopadu 2005. zbog osobnih razloga.
Zajec stigao u Maksimir na završnu rundu pregovora!
Velimir Zajec stigao je u maksimirske odaje kako bi finiširao pregovore sa Zdravkom Mamićem i potpisao ugovor s Dinamom. Ukoliko završni razgovori urode plodom, u što ne treba sumnjati, novi trener 'modrih' bit će predstavljen na tiskovnoj konferenciji točno u podne.