Knuth comenzó el proyecto, originalmente concebido como un libro único con doce capítulos, en 1962. Los primeros tres volúmenes de lo que se esperaba que fuera un set de siete volúmenes se publicaron en 1968, 1969 y 1973. El trabajo comenzó en serio en Volume 4 en 1973, pero fue suspendido en 1977 por trabajar en composición tipográfica. La escritura de la copia final del Volumen 4A comenzó a mano en 2001, y el primer pre-fascículo en línea, 2A, apareció más tarde en 2001. La primera entrega publicada del Volumen 4 apareció en rústica como Fascículo 2 en 2005. La tapa dura Volumen 4A, que combina el Volumen 4, Fascículos 0–4, se publicó en 2011. El Volumen 4, Fascículo 6 (“Satisfacción”) se lanzó en diciembre de 2015 ; El Volumen 4, Fascículo 5 (“Preliminares matemáticos Redux; Backtracking; Dancing Links”) se lanzó en noviembre de 2019.

Se espera que los fascículos 5 y 6 comprendan los primeros dos tercios del Volumen 4B. Knuth no ha anunciado ninguna fecha estimada para el lanzamiento del Volumen 4B, aunque su método utilizado para el Volumen 4A es liberar el volumen de tapa dura en algún momento después del lanzamiento de los fascículos en rústica que lo componen. Las estimaciones de los editores a corto plazo establecen la fecha de lanzamiento en mayo o junio de 2019, lo que resultó ser incorrecto.