V době studia na gymnáziu se s ním rodiče přestěhovali ze Slezska do Prahy. V prosinci roku 1939 složil zkoušky do elévského sboru – soukromé herecké školy E. F. Buriana, založené při jeho slavném divadle D40. K pedagogům zde kromě Buriana patřila např. Lola Skrbková a Nina Jirsíková. Původně se tu chtěl zlepšit v tanci (uměl stepovat a dokonce vedl i taneční kurs), ale Burian si všiml jeho talentu a doporučil mu dráhu hereckou. V sezóně 1939/1940 se začal Brodský objevovat ve sboru v Burianových hrách, prvním samostatným jevištním projevem bylo pak v D41 vystoupení v Zeyerově Staré historii, kde ztvárnil úspěšně několik osob a předmětů, např. muzikanta, nosiče, okno a zámek. Když nacisté v roce 1941 Buriana zatkli a divadlo zavřeli, chvíli ještě setrval ve zde ustanoveném a Františkem Salzerem vedeném Divadle Na Poříčí, třetí scéně Divadla na Vinohradech, později společně s ostatními spolužáky pomohl rozběhnout pololegální divadlo Větrník. Divadlo sídlilo v letech 1941 – 1944 v Divadélku pro 99 ve výstavní síni U Topičů na Národní třídě, v roce 1944 pak krátce v Ženském klubu v ulici Ve Smečkách. Ve Větrníku byli partnery Brodského například Zdeněk Míka, Zdeněk Řehoř, Stella Zázvorková a konzervatoristé Jaromír Pleskot a Radovan Lukavský. Souběžně s působením ve Větrníku hrál i v Pražském dětském divadle Míly Mellanové. V roce 1944 odešel z Větrníku a založil spolu s několika kolegy Pražské divadelní studio, které se však po nezdařené jedné premiéře rozpadlo.

Vlastimil Brodský, bronzový portrét od Stanislava Hanzíka, Foyer Národního divadla v Praze
Vrátil se zpět do Větrníku a v květnu 1946 odešel s několika herci do Divadla satiry (tehdy ještě nesídlilo na své pozdější scéně ve Vodičkově ul.), kde působil v sezóně 1946 – 47 a na chvíli se pak ještě vrátil k E. F. Burianovi do divadla D 47.

Zklamán tehdejším uměleckým a politickým směřováním svého mistra, přešel nakonec se skupinou mladých herců (O. Krejča, A. Hegerlíková, Z. Řehoř, Z. Dítě) za Jiřím Frejkou do Divadla na Vinohradech , kde setrval i po Frejkově odchodu a po vzniku Divadla československé armády a byl členem souboru až do roku 1990 a i později zde působil jako stálý host.

V postavách, které ztvárnil, objevoval lidskou obyčejnost, své postavy vystihoval poetickou zkratkou, jeho komika byla označována za neobyčejně lidskou. Býval charakterizován jako typ herce tragikomického.

Od roku 1946 se objevoval pravidelně ve filmu. Spolupracoval např. s Otakarem Vávrou, Martinem Fričem a našel společný umělecký pohled se Zdeňkem Podskalským, v jehož několika filmech se později objevil. Jako jediný český herec získal cenu Berlínského mezinárodního filmového festivalu Zlatý medvěd za roli v německém filmu Jakub lhář, zápornou postavu si zahrál i v oscarovém snímku Ostře sledované vlaky. V roce 2002 získal Českého lva za nejlepší mužský herecký výkon v hlavní roli ve filmu Babí léto.

Jednalo se také o výborného rozhlasového a dabingového herce, několik desítek let působil v Československém rozhlase jakožto populární skřítek Hajaja, jenž předčítal každý den dětem pohádky na dobrou noc. Na gramofonových deskách vyšly Hajajovy pohádky (vyd. Supraphon), Brodský namluvil také např. postavu Švejka v Osudech dobrého vojáka Švejka (vyd. Ultraphon), Bondyho ve Válce s mloky (vyd. Supraphon) nebo Taťku Šmoulu v seriálu Šmoulové.

Z rozvedeného prvního manželství s tenistkou Bíbou Křepelkovou pochází jeho syn Marek Brodský a z rozvedeného druhého manželství s herečkou Janou Brejchovou pochází jeho dcera Tereza Brodská, herečka.

Dne 20. dubna 2002 spáchal sebevraždu.

Je po něm pojmenována ulice v Praze.

Pohřben je spolu s rodiči ve Slunečné, kde měl chalupu, na tamním hřbitově.