Živojinović se narodil ve městě Koraćica v Srbsku (tehdy Království Jugoslávie), v podhůří Kosmaj. Jeho herecký talent se projevil již v 15 letech, zatímco pracoval jako kulisák v akademickém divadle v Bělehradě. Poté, co ukončil hereckou školu v Užici a Novém Sadu, snažil se zapsat na akademii dramatu v Bělehradě a uspěl až na třetí pokus.
Velimir Živojinović dával zpočátku přednost hraní v divadle před filmovými rolemi. Na plátně debutovat v roce 1955 ve filmu PESMA SA KUMBARE (Obléhání Bělehradu), což byl začátek jeho neuvěřitelně plodné kariéry. Živojinović, se brzy stal známým pod přezdívkou "Bata". Za 45 let hercké dráhy ztvárnil více filmových rolí než jakýkoli jiný herec v historii bývalé Jugoslávie a pouhá velikost jeho filmografie pravděpodobně nebude v blízké budoucnosti překonána.
Počet Živojinovićových rolí nebyl jen obrovský (na 300 filmů a TV seriálů), ale i velmi všestranný. Hrál jak hrdiny, tak darebáky a snadno "přepnínal" mezi hlavními a vedlejšími rolemi. Už v šedesátých letech se etabloval jako jedna z největších hvězd filmů bývalé Jugoslávie. Zenit jeho popularity stoupal i v akčních válečných snímcích v sedmdesátých létech (BITVA NA NERETVĚ, VALTER BRÁNÍ SARAJEVO, SOUTĚSKA, MUŽI S GRANÁTY, PARTYZÁNI a další.). K jeho nejlepším známým filmům z tohoto období patří i MISTR A MARKÉTKA, DERVIŠ A SMRT, HLÍDAČ PLÁŽE V ZIMNÍM OBDOBÍ, SKUPINOVÝ PORTRÉT S DÁMOU a PES, KTERÝ MĚL RÁD VLAKY. V osmdesátých létech Živojinović vytvořil sebeparodující obraz akčního hrdiny v sérii veselých komedií.
V roce 1990 byl zvolen do Srbského parlamentu. Od roku 1991 je aktivní na srbské politické scéně jako člen Socialistické strany Srbska. V srpnu 1993 získal cenu za celoživotní dílo "Slavica ".
