Vystudoval Konzervatoř v Praze. Vystupoval s mnoha předními jazzovými formacemi (S+HQ Karla Velebného, Big Band Radio Prague, Jazz Cellula, E.Viklický, J. Stivín, K.Růžička, Super Quartet, G.Brom a v mnoha daších doma i v zahraničí) a hudebníky (Gerge Mraz, Tony Scott, John Surman, Lou Blackburn, Benny Bailey, Joe Newman, Ted Curson, Barre Phillipss, Toots Thilemans, Dave Friedman, Scott Robinson, Sonny Costanzo a další). Hrál na významných jazzových festivalech (Ost West Jazz Festival Nürnberg, Jazz Jamboree Warszawa, International Jazz Festival Prague, Montreal Jazz Festival, Chicago, Jazz Festival on Red See /Izrael/ a mnoha dalších), mnohokrát vyhrál jako bubeník anketu All Stars Band a reprezentoval u nás i v zahraničí (naposledy 2006 na Přerovském jazzovém festivalu) a získal několik ocenění: 1967 - 1. místo ve hře na bicí nástroje v celostátní soutěži jazzových hudebníků, 2005 - platinová deska od Supraphonu, 2005-6 zvítězil v hitparádě Českého rozhlasu 2 - Praha.
Nahrál mnoho jazzových CD (SHQ - Motus, Jazzové nebajky, Týnom tánom, SHQ & Woodwind Quintet ...., JOČR - Jazzový orchestr Československého rozhlasu - Jazz ze studia A, Jazz Celulla - Oheň až požár, ...., Joe Newman - MIDGEST , Jiří Stivín - INSPIRATION WITH FOLKLOR, Emil Viklický- ROUND MIDNIGHT, Scott Robinson - MAGIC EYE, Harald Gundhus - BOHEMIEN HIGHTS, Benny Bailey - I REMEMBER LOVE, Pavel Šporcl - NOVELTY CONCERTO) a jako Band leader se podílel na albech Big Band Radio Praha - Walkin´ and Talkin´(jako skladatel a dirigent), Josef Vejvoda Trio - One Minute Dance, Josef Vejvoda Trio & Benny Bailey - A Meeting To Build A Dream On.

J.Vejvoda napsal mnoho skladeb pro trio, kvartet, kvintet, oktet a bigband, v poslední době píše zejména skladby pro trio a symfonický nebo komorní orchestr (NOVELTY CONCERTO, CELBRATION, BRASILIAN PEARL JUBILEE, THREE LITTLE LOVES, POCTA JAROSLVU JEŽKOVI).

V roce 2002 se mu dostalo výjimečné příležitosti dirigovat v téměř vyprodané newyorkské Carnegie Hall Hudbu Hradní stráže a Policie České republiky. Josef Vejvoda je kapelníkem i dalších orchestrů "Vejvodovy kapely a "Salonního orchestru" s nimiž natočil celkem 15 alb. Jako hostující dirigent působí u orchestrů doma i v zahraničí.