Cinquième des sept enfants de José Telles Velloso (surnommé "Seu Zezinho") et de Claudionor Vianna Telles Velloso ("Dona Canö), il est né à Santo Amaro da Purificação, dans l'État de Bahia. Il choisit le prénom de sa petite sœur (sixième enfant de la famille), Maria Bethânia, d'après une chanson célèbre de l'époque de Nelson Gonçalves. Sa sœur, chanteuse elle aussi, le précéda d'ailleurs dans la célébrité dans les années 1960.
Il commença sa carrière en chantant de la bossa nova et cita d'ailleurs comme ses plus grandes influences de l'époque João Gilberto et Dorival Caymmi. (João Gilberto dira d'ailleurs plus tard à propos de la contribution de Caetano à la musique brésilienne : « il a ajouté une dimension intellectuelle à la musique populaire brésilienne ».). Très vite, il abandonna un "l" de son nom et opta pour Caetano Veloso. Avec l'influence des Beatles, ses collaborations avec
Gilberto Gil,
Gal Costa, Tom Zé, Chico Buarque et Os Mutantes débouchèrent sur le tropicalisme, qui mêle la pop brésilienne avec le rock roll et de la musique d'avant-garde, avec pour résultat un son plus international, psychédélique et socialement engagé. Le positionnement politique de Veloso, résolument à gauche, lui valut de nombreux ennuis avec la junte militaire qui gouverna le Brésil jusqu'en 1985. Ses chansons furent fréquemment censurées et certaines interdites. Veloso fut aussi mis à l'écart de la gauche socialiste brésilienne à cause de ses influences musicales « non nationales » (comme le rock roll). Veloso et
Gilberto Gil passèrent plusieurs mois en prison pour « activités anti-gouvernementales » en 1968 et durent même s'exiler à Londres. L'œuvre de Veloso après son retour au Brésil en 1972 fut caractérisé par des appropriations constantes, non seulement de styles étrangers, mais aussi de styles et de rythmes folkloriques brésiliens à moitié oubliés. En particulier, la célébration de la culture afro-brésilienne de Bahia qui peut être vu comme le précurseur d'un groupe afro-centrique comme Timbalada.
Dans les années 1980, la popularité de Veloso s'accrut à l'extérieur du Brésil, particulièrement en Israël, au Portugal et en France. En 1997 Veloso sortit un livre sur ses premières années et le Tropicalisme(encore appelé Tropicália), Verdade Tropical. En 2006, il est l'une des pop-stars internationales les plus respectées et prolifiques, avec plus de 50 enregistrements disponibles et des participations à des bandes originales de film comme Frida.
Grand amateur des répertoires populaires hispano-américains et états-uniens, il commercialise en 1994 son premier album entièrement chanté en espagnol intitulé Fina Estampa, sous l'impulsion initiale de sa maison de disque. En 2004, alors que les États-Unis d'Amérique font l'objet de vives critiques en général sur la scène internationale, il en profite pour réaliser un ancien projet qui lui tenait à cœur : A Foreign Sound, son premier album entièrement en anglais, et qui comprend des reprises de standards américains allant de Love For Sale composée initialement par Cole Porter à "Come as you are" de Nirvana, en passant par les oeuvres de
Bob Dylan, Stevie Wonder, Arto Lindsay ou encore
Nat King Cole.
La fin des années 2000 marque le retour vers un son plus rock avec l'album Cê et le live Cê ao Vivo enregistré lors de la tournée accompagnant l'album studio. A cette occasion Caetano Veloso tourne la page Jaques Morelenbaum pour s'entourer de musiciens trentenaires emmenés par Pedro Sá. Quelques mois après il prolonge cette approche musicale en compagnie du groupe désormais baptisé banda Cê, tout en se rappropriant le samba. Zii E Zie, son nouvel opus, sort dans les bacs en 2009 après que la plupart des chansons ont été jouées sur scène et présentées sur son blog internet Obra Em Progresso.