Foster nació en Richmond, Virginia, y creció en Nueva York. Comenzó a tocar la batería a la edad de trece años e hizo su debut discográfico con Blue Mitchell a los veintiún.

Se unió a Miles Davis cuando Jack DeJohnette lo dejó en 1972,^[2]​ y tocó con Davis hasta 1985. Foster tocó con Miles Davis durante la década de los 70, y fue una de las pocas personas que tuvo contacto con Davis durante su retiro de 1975 a1981. Foster también tocó con Davis en 1981, en su álbum de regreso The Man with the Horn. En su autobiografía de 1989, Davis describe la primera vez que oyó a Foster tocar en vivo en 1972, en el Cellar Club en Manhattan: "Él [Foster] me llamó la atención porque se hacía un hueco y se encontraba bien allí. Ese era el tipo de cosa que yo estaba buscando."

Foster comenzó a componer en la década de los 70, y ha hecho giras con su propia banda, incluyendo a músicos como el bajista Doug Weiss, el saxofonista Dayna Stephens, y el pianista Adam Birnbaum.

Foster ha realizado giras con Herbie Hancock, Sonny Rollins, y Joe Henderson. Es un batería versátil que ha tocado en estilos musicales que van desde el bebop al free jazz y a la música de jazz/rock.

• Mixed Roots (1978)
• Brandyn (1996, Laika) Con Chris Potter, Dave Kikoski, Doug Weiss
• Oh! (ScoLoHoFo) (2003) Con Joe Lovano, John Scofield, Dave Holland
• Love, Peace and Jazz! Live at the Village Vanguard (2008, JazzEyes) Con Eli Degibri, Kevin Hays, Doug Weiss
• The Paris Concert (DVD – 2008, Inakustic Gmbh) Con Eddie Henderson, Eli Degibri, Aaron Goldberg, George Colligan, Doug Weiss

Con Kenny Barron

• Landscape (Baystate, 1984)
• Super Standard (Venus, 2004)

Con Joanne Brackeen

• Havin' Fun (Concord Jazz, 1985)
• Fi-Fi Goes to Heaven (Concord Jazz, 1986)

Con Miles Davis

• In Concert: Live at Philharmonic Hall (1973)
• Big Fun (1974)
• Get Up with It (1974)
• Dark Magus (1974)
• Agharta (1975)
• Pangaea (1976)
• The Man with the Horn (1981)
• We Want Miles (1981)
• Star People (1983)
• Decoy (1984)
• You're Under Arrest (1985)
• Amandla (1989)
• Miles Davis at Newport 1955-1975: The Bootleg Series Vol. 4 (Columbia Legacy, 2015)

Con Tommy Flanagan

• Giant Steps (Enja, 1982)

Con Dexter Gordon

• Biting the Apple (SteepleChase, 1976)

Con Jimmy Heath

• New Picture (Landmark, 1985)

Con Illinois Jacquet

• The Soul Explosion (Prestige, 1969)

Con Duke Jordan

• Duke's Delight (SteepleChase, 1975 [1976])
• Lover Man (SteepleChase, 1975 [1979])

Con Yusef Lateef

• The Doctor is In... and Out (Atlantic, 1976)

Con Blue Mitchell

• The Thing to Do (Blue Note, 1964)
• Down with It! (Blue Note, 1965)

Con Art Pepper

• New York Album (Galaxy, 1979 [1985])
• So in Love (Artists House, 1979)

Con Sonny Rollins

• Don't Ask (1979)
• Love at First Sight (1980)
• Here's to the People (1991)
• Sonny Rollins + 3 (1995)

Con David Liebman

• Pendulum (Artists House, 1979)

Con Bud Shank

• This Bud's for You... (Muse, 1984)

Con McCoy Tyner

• Horizon (1979)
• Quartets 4 X 4 (1980)
• It's About Time (con Jackie McLean, 1985)
• New York Reunion (1991)
• McCoy Tyner Plays John Coltrane (1997)
• McCoy Tyner with Stanley Clarke and Al Foster (1998)

Con Cedar Walton

• Animation (Columbia, 1978)
• Soundscapes (Columbia, 1980)
• Seasoned Wood (HighNote, 2008)

Con Steve Kuhn

• The Vanguard Date with Ron Carter (Sunnyside/E1, 1986)
• Life's Magic con Ron Carter (Sunnyside/E1, 1986)
• Seasons of Romance (Postcards, 1995)
• Live at Birdland with Ron Carter (Blue Note, 2006)

Con otros

• Reconstruction. Hugh Masekela (Uni, 1970)
• Brooklyn Brothers. Cecil Payne and Duke Jordan (Muse, 1973)
• Silver 'n Brass. Horace Silver (1975)
• Dune. Sam Morrison, (1976)
• Bird Gets the Worm. Cecil Payne (Muse, 1976)
• Witches, Goblins, Etc. Sadik Hakim, (1978)
• Everything Must Change. Johnny Lytle, (1978)
• In, Out And Around. Mike Nock, (1978)
• Paradise Space Shuttle. George Adams, (1979)
• Elegie For Bill Evans. Richie Beirach, (1981)
• The State of the Tenor, Vols. 1 & 2. Joe Henderson, (1985)
• Illusions. Eliane Elias, (1986)
• So Near, So Far. Joe Henderson, (1992)
• Pure. Chris Potter, (Concord 1994)
• Time Well Spent. Andy LaVerne y George Mraz, 1994)
• Celebrating Sinatra. Joe Lovano, (1996)
• I Remember Miles. Shirley Horn, (1998)
• The Montreal Tapes: Tribute to Joe Henderson (Verve, 1989 released 2004) (con Charlie Haden and Joe Henderson)
• Peter Zak Trio. Peter Zak, Paul Gill, (2004)
• Israeli Song. Eli Degibri, (2010)