Runsaat kymmenen vuotta orkesterissa toiminut Foster sävelsi ja sovitti Basielle lukuisia kappaleita, joista tunnetuimmaksi tuli orkesterin vakio-ohjelmistoon jäänyt ”Shiny Stockings”.
Kirjoitustyön ohella Foster oli yksi Basien keskeisistä solisteista, jonka jykevä tenorityyli loi hyvän kontrastin orkesterin toiselle tenorisolistille, pehmeämpisoundiselle Frank Wessille. Hyvän mahdollisuuden vertailla näiden kahden tenoristin tyylejä tarjosi Neil Heftin heille kirjoittama kappale ”Two Franks”, jonka Basien orkesteri levytti 1954.
Basie-aikanaan Foster sai useita tarjouksia muiltakin kapellimestereilta. Häntä kosiskelivat mm. Thelonious Monk ja Miles Davis, mutta Foster piti varmempana Basien tarjomaa vakaata toimeentuloa. Tosin Foster levytti Monkin kanssa 1954. Foster teki 1950-luvulla monia pikkuyhtyelevytyksiä omissa nimissään ja myös mm. Elmo Hopen, Donald Byrdin ja Kenny Burrellin kanssa.
Erottuaan Basien orkesterista 1964 Foster toimi sovittajana Sarah Vaughanille, Frank Sinatralle, Woody Hermanille ja Benny Goodmanille sekä levytti erilaisten kokoonpanojen kanssa. Hän myös soitti muutaman vuoden vaimonsa serkun rumpali Elvin Jonesin yhtyeessä.
Oman Loud Minority-orkesterinsa Foster kokosi 1970-luvun alussa. Tämän ison orkesterin musiikki oli selvästi sävyiltään selvästi modernimpaa kuin hänen Basielle tekemät työt. Loud Minority teki useita levyjä 1970-luvulla, jotka tosin ovat nykyään vaikeasti saatavissa.
Loud Minority toimi kuitenkin enemmän tai vähemmän tilapäisluontoisesti, joten Fosterille jäi hyvin myös aikaa erilaisille free lance-hankkeille pääasiassa arvostettuna sovittajana hyvinkin erityylisten artistien taustalla. Tämän lisäksi hän toimi myös opettajana eriasteisissa oppilaitoksissa.
Foster palasi vielä uudelleen 1984 kuolleen Basien musiikkiin johtaen orkesteria useita vuosia 1986 alkaen.
Vaikka Fosterin oma soitto katkesi 2001 halvauksen johdosta, hän jatkoi kirjoittamista tehden sovituksia mm. Lincoln Center Orchestralle. 2000-luvulla toimi aktiivisesti järjestötyössä jazz-muusikkojen hyväksi.
Suomessa Foster kävi ensimmäistä kertaa 60-luvun alussa tuolloin Basien riveissä. Ensimmäisen oman orkesterinsa hän toi Suomeen 1978, jolloin Living Colour-nimellä esiintynyt 12-henkinen kokoonpano soitti sekä Porissa että teki myös lp:n Edward Vesalan perustamalle Leo-yhtiölle. 1980-luvulla Fosterin käynnit tihenivät Suomessa. Tuolloin hän kävi useita kertoja Porissa sekä omien yhtyeidensä kanssa että irtosolistina. Hän myös johti Pori Big Bandia 1980. Monilla vierailullaan erittäin sympaattiseksi ihmiseksi osoittautunut Foster toi vielä 1997 Poriin täysimittaisen big bandin.
Hienon muusikon kuolinsyynä olivat munuaisten toimintaongelmat.
