Uno de los grandes baterías de jazz, miembro de la banda de Miles Davis durante 13 años, la contribución de Foster a la música está articulada por el propio Davis en su autobiografía de 1989, Miles.
Crecer en Harlem le brindó a Al la oportunidad de disfrutar de muchos espectáculos excelentes en el teatro Apollo. Escuchó a Miles Davis en directo en 1958 con su sexteto, que incluía a John Coltrane, Cannonball Adderly, Bill Evans, Paul Chambers y Jimmy Cobb. Otras experiencias memorables incluyen la batalla de tambores de Buddy Rich y Philly Joe Jones, los Jazz Messengers de Art Blakey con Lee Morgan, el Cuarteto de Dave Brubeck y el Cuarteto de John Coltrane. Estas experiencias lo engancharon a la música. Su padre, bajista aficionado, le compró una batería y practicaba todos los días después del colegio.
Su primera gran oportunidad en la industria musical llegó en 1964, cuando se unió al grupo de Blue Mitchell en la grabación clásica The Thing To Do para Blue Note Records. Grabado en el estudio de Rudy Van Gelder, con la producción de Alfred Lion, este disco se ha convertido en un clásico. En él aparecen Blue Mitchell (trompeta), Junior Cook (tenor), un joven Chick Corea (piano) y Gene Taylor (bajo).
Es único entre los bateristas del jazz, ya que sus composiciones han sido reconocidas por algunos de los artistas más destacados. El pianista Hank Jones grabó tres de sus composiciones: Papa Joe, Just Before Dawn y Pauletta, para su álbum For My Father. Eric Reed grabó su composición emblemática, Brandyn, y el saxofonista Chris Potter grabó Bonnie Rose para su álbum Pure de Verve. El trompetista Eddie Henderson grabó la composición de Al Missing Miles en For All We Know. El propio Foster grabó su primera grabación como líder, Mixed Roots, en 1977. Se unió al grupo de Miles Davis cuando Jack DeJohnette lo dejó en 1972, y tocó con Davis hasta 1985. Durante este período, Foster contribuyó a varios álbumes clave, incluyendo Big Fun (1974), Get Up with It (1974), Agharta (1975) y Pangaea (1976).
