Hij was de zoon van een gitarist en speelde op zijn twaalfde bongo en maraca in de band van zijn vader. Halverwege de jaren zestig ging hij naar Rio de Janeiro, waar hij werkte met zanger Milton Nascimento. In 1970 nam saxofonist Gato Barbieri hem in zijn band op. De groep maakte een uitgebreide toer (onder meer op het Montreux Jazz Festival) en nam een aantal platen op. Na de toer woonde Vasconcelos in Parijs en nam daar zijn eerste album op, Africa Deus. Ook speelde hij af en toe met trompettist Don Cherry in Zweden. Na zijn terugkeer in Brazilië ging hij samenwerken met gitarist en fluitist Egberto Gismonti, met wie hij verschillende platen maakte, zoals Dança das Cabeças.
In 1978 vormde hij in New York met Don Cherry en Collin Walcott (tabla, sitar) de groep Codona, die een mengeling van verschillende soorten muziek maakte. De naam was een acroniem van de eerste letters van de voornamen. De groep was actief tot de dood van Walcott in 1984. In diezelfde tijd speelde Vasconcelos als gast in de groep van Pat Metheny (1980-1983). In 1986 maakte Vasconcelos een solo-tournee door zijn geboorteland.
