Lins wurde in Rio geboren, wuchs aber in der Kindheit teilweise in Boston auf, wo sein Vater am MIT Schiffbau studierte. Nach der Schulausbildung an einer Militärschule in Rio studierte er an der Universität von Rio Chemie-Ingenieurwesen (Abschluss 1969). Nebenbei strebte er eine Volleyball-Karriere an, entdeckte dann aber sein musikalisches Talent. Mit 18 Jahren brachte er sich das Klavierspiel nach Gehör bei und fing an, Jazz und Bossa Nova zu spielen. 1968 kam er mit seiner Komposition „Até o Amanhecer“ in die Endrunde des Festival Universitário da TV Tupi. 1969 übernahm Elis Regina seinen Song „Madalena“, der (auch in Europa) ein Hit wurde. 1970 spielte sie seine Komposition „O Amor é o meu País“, die später von der VARIG beim Einsteigen der internationalen Passagiere in ihren Flugzeugen abgespielt wurde.
Lins leitete gemeinsam mit Aldir Blanc, Gonzaguinha und anderen das Programm Som Livre Exportação auf dem Fernsehsender TV-Globo. Seit 1970 erschienen regelmäßig Alben von ihm unter eigenem Namen als Sänger. Sein 1974 veröffentlichtes Album Modo livre enthielt den Hit „Abre Alas“ mit einem Text von Vítor Martins. 1977 hatte er einen weiteren großen Erfolg mit der Single „Somos todos iguais nesta Noite“.
Ab 1985 nahm er seine Musik in den USA auf und ging international auf Tourneen. Für das George-Benson-Album Give me the Night steuerte er den Titel Dinorah, Dinorah bei. Produzent Quincy Jones engagierte ihn daraufhin für sein Album The Dude, wo er für Velas einen Grammy in der Kategorie „Best Jazz Performance“ erhielt. Auch auf Quincy Jones´Album Back on the Block, das ebenfalls einen Grammy gewann, ist eine Komposition von ihm vertreten (Setembro), und er steuerte auch Kompositionen für das Manhattan Transfer-Album Brazil bei. Mit dem Jazz-Trompeter Terence Blanchard nahm er das Album The Heart Speaks auf, das überwiegend Kompositionen von Lins enthielt (Lins als Pianist und als Sänger). 1987 arbeitete er mit den Crusaders zusammen auf Life in the Modern World (mit zwei seiner Kompositionen Life in the Modern World und Some People Will Never Learn). 1989 erschien sein Album Love Dance (ein weiterer seiner Standards), das erste, auf dem er englisch singt. Mit Toots Thielemans nahm er Brazil 1 and 2 auf, mit Lee Ritenour und Dave Grusin das Fusionjazz-Album Harlequin (1985).
Als Filmkomponist lieferte er den Soundtrack für den brasilianischen Film Dois Córregos. Als Musikproduzent förderte er Sänger wie Chico César, Lenine und Belô Veloso.
Im Oktober 2000 gab es ein Tribute-Konzert in der Carnegie Hall in New York zu seinen Ehren (als Album A Love Affair bei Telarc erschienen).
Lins genießt in seiner brasilianischen Heimat so große Popularität, dass er auch die Auseinandersetzung mit dem früheren Militär-Regime des Landes nicht scheuen musste.
