Hijo de un funcionario público y de un ama de casa, la popular doña Canô, desde pequeño Caetano Veloso manifestó interés por la música, la pintura y, después, por el cine.
En 1959, un amigo le hizo conocer el disco Chega de saudade, de João Gilberto, que lo marcó profundamente: Caetano considera al guitarrista bahiano el responsable por haber seguido una carrera artística. En los años 60, en Salvador, escribió críticas de cine para el Diário de Notícias, aprendió a tocar la guitarra y se presentó en bares junto a su hermana, Maria Bethânia. En 1963 ingresó en la Facultad de Filosofía de la Universidad Federal de Bahía, y conoció a Gilberto Gil, Gal Costa y Tom Zé.
En 1965 lanzó su primer sencillo, con las composiciones “Cavaleiro” y “Samba em paz”. Acompañando a Maria Bethânia, que sustituiría a Nara Leão en el show Opinião, se dirigió entonces a Río de Janeiro. En la década de 1960 participó en importantes festivales de música popular y compuso bandas sonoras para cine. En 1967 lanzó su primer disco, titulado Domingo, junto a Gal Costa. Ese mismo año presentó, en el III Festival de Música Popular Brasileña (MPB) de TV Record, la marcha “Alegria, alegria”, que obtuvo el cuarto lugar en el certamen.
Al año siguiente participó del movimiento Tropicalismo, considerado de vanguardia en la MPB. El disco Tropicália ou panis et circensis, realizado en colaboración con Gil, Gal Costa, Tom Zé, Torquato Neto, Rogério Duprat, Capinan y Nara Leão, representó la concreción del Tropicalismo.
En 1968, en la fase más represiva del régimen militar brasileño, su canción “É proibido proibir” fue abucheada y desclasificada, lo que le provocó una fuerte indignación. “Ustedes no están entendiendo nada”, dijo. En 1969, tras un período en prisión por “faltar el respeto al himno y la bandera nacional”, partió al exilio político en Londres, donde compuso músicas como “London, London” y “Como dois e dois”. Regresó a Brasil en 1972, donde realizó varios shows en distintos lugares del país y trabajó, en los años siguientes, como productor.
En 1976, Caetano, Gal, Gil y Maria Bethânia formaron el grupo Doces Bárbaros. Al año siguiente lanzó su primer libro, Alegria, alegria, una compilación de artículos, manifiestos, poemas y entrevistas al poeta Waly Salomão. En los años 80 continuó grabando, y produjo los discos Outras palavras; Cores, nomes; Uns y Velô. Junto a Chico Buarque de Holanda presentó, en 1986, el programa de televisión Chico e Caetano, en el que cantaba y presentaba a distintos invitados. En los años 90 lanzó Tropicália 2 (1993) con Gilberto Gil y, en 1997, el libro Verdade tropical (Verdad tropical) . El disco Livro (1998) recibió el premio Grammy en 2000 en la categoría de mejor disco de MPB. En 2001 participó del filme Hable con ella, de Pedro Almodóvar, cantando “Cucurrucucú paloma”. En 2003, su interpretación de “Burn it blue” junto a la mexicana Lila Dows, representando el filme Frida en la ceremonia de entrega de los Oscar, fue la primera participación de un cantante brasileño en tal evento. Ese mismo año ganó el Grammy latino en la categoría de mejor álbum de MPB, por el CD Eu não peço desculpas, trabajo realizado en colaboración con Jorge Mautner.
El 25 de enero de 2004 se presentó en la esquina de las avenidas Ipiranga y São João, en São Paulo, en el 450 aniversario de la ciudad. Ese año lanzó su primer CD en inglés, A foreign sound, en el que interpretó “Come as you are”, de la banda norteamericana Nirvana. Al año siguiente presentó una colección de ensayos y críticas publicadas a lo largo de su carrera en diarios y revistas, bajo el título O mundo não é chato, organizada por el poeta Eucanaã Ferraz.
En 2007 fue lanzada la discografía oficial del artista por la grabadora Universal Music, en conmemoración a sus 40 años de carrera. En 2008, Caetano y el cantante Roberto Carlos hicieron juntos un show en tributo a Antônio Carlos Jobim y grabaron el CD y DVD Roberto Carlos y Caetano Veloso y la música de Tom Jobim. Caetano lanzó los discos Cê (2006), Obra emProgresso (2008) y Zii e Zie (2009). En 2011 produjo y compuso todas las canciones de Domingo de Gal Costa. En 2013 recibió el Grammy Latino en la categoría de Mejor Álbum de Compositor por Abraçaço.
Fue electo el cuarto mejor artista de música brasileña y el octavo mayor cantante brasileño de todos los tiempos por la revista Rolling Stone. En 2015, Caetano salió de gira por Brasil y al exterior con Gilberto Gil, ambos conmemorando 50 años de carrera con el espectáculo Dois Amigos, um século de música.