Nacido en Chicago y criado en Boston, Williams comenzó sus estudios con el maestro batería Alan Dawson a una edad temprana y comenzó a tocar profesionalmente a la edad de 13 años con el saxofonista Sam Rivers. Jackie McLean contrató a Williams a los 16 años. A los 17 años Williams encontró una fama considerable con Miles Davis, uniéndose a un grupo que más tarde fue apodado «Second Great Quintet» (Segundo Gran Quinteto) de Davis. Su primer álbum como líder, Life Time de 1964 (que no debe confundirse con el nombre de su banda «Lifetime», que formó varios años más tarde) fue grabado durante su mandato con Davis.

Williams era un elemento vital del grupo, llamado por Davis en su autobiografía «el centro del sonido del grupo». Su inventiva interpretación ayudó a redefinir el papel de la sección rítmica de jazz a través del uso de polirritmos y modulación métrica (transición entre tempos matemáticamente relacionados y/o firmas de tiempo). Pero quizás su logro principal fue demostrar, a través de su interpretación, que el baterista no necesita ser relegado al cronometraje y al acompañamiento en un conjunto de jazz; que el baterista puede ser libre de contribuir a la interpretación como un socio igualitario en la improvisación.

En 1969, formó un trío, «The Tony Williams Lifetime», con John McLaughlin a la guitarra y Larry Young al órgano. Fue una banda pionera del movimiento de fusión, una combinación de rock, R&B y jazz. Su primer álbum, Emergency! fue ampliamente rechazado por la comunidad de jazz en el momento de su lanzamiento. Sin embargo, Miles Davis quedó tan impresionado con el álbum y su dirección altamente experimental que pidió encabezar el grupo como si fuera suyo; Williams declinó. Hoy en día, Emergency! es considerado por muchos como un clásico de la fusión.

Después de la partida de McLaughlin, y varios álbumes más, Lifetime se disolvió. En 1975, Williams formó una banda llamada «The New Tony Williams Lifetime», con el bajista Tony Newton, el pianista Alan Pasqua y el guitarrista inglés Allan Holdsworth, que grabaron dos discos para Columbia Records, Believe It y Million Dollar Legs respectivamente.

A mediados de 1976, Williams fue parte de una especie de reunión con sus viejos compatriotas de la banda Miles Davis, el pianista y tecladista Herbie Hancock, el bajista Ron Carter y el saxofonista tenor Wayne Shorter. Miles se retiró de la reunión en el último minuto y fue reemplazado por Freddie Hubbard. El disco fue lanzado más tarde como V.S.O.P. (que significaba «Very Special OneTime Performance») y fue muy útil para aumentar la popularidad del jazz acústico. El grupo realizó giras y grabaciones durante varios años, editando una serie de discos en directo bajo el nombre «V.S.O.P.» o «The V.S.O.P. Quinteto». (Las reediciones de estos álbumes se venden bajo el nombre de Herbie Hancock, lo que hace que las cosas sean un poco confusas, ya que el álbum original V.S.O.P., que solo era un álbum de Hancock, nunca ha sido lanzado en CD).

En 1985, Williams grabó un álbum para Blue Note Records titulado Foreign Intrigue, que incluía la interpretación del pianista Mulgrew Miller y el trompetista Wallace Roney. Más tarde ese mismo año formó un quinteto con Miller y Roney en el que también participaron el saxofonista tenor y soprano Bill Pierce y el bajista Charnett Moffett (más tarde Ira Coleman). Esta banda tocó las composiciones de Williams casi exclusivamente (la canción de Lennon/McCartney «Blackbird», el estándar «Poinciana», y el blues de Freddie Hubbard «Birdlike» siendo la excepción) y realizó giras y grabaciones durante el resto de los años 80 y principios de los 90. Esta sección rítmica también se grabó en trío.

Williams vivió y enseñó en el área de la bahía de San Francisco hasta su muerte por un ataque cardíaco después de una cirugía rutinaria de vesícula biliar. Una de sus grabaciones finales fue Arcana, un lanzamiento organizado por el prolífico bajista Bill Laswell.