Tam kontynuowali działalność muzyczną pod kierunkiem producenta Ralpha Mace’a.
W 1969 ożenił się ze studentką Andréa Gadelha, znaną jako Dedé, siostrą Sandry Gadelha, byłej żony Gilberto Gila; w 1972 urodził im się syn Moreno, który w przyszłości również został piosenkarzem.
W 1972 Veloso powrócił do Brazylii i ugruntował swoją pozycję dojrzałego piosenkarza, umiejętnie łączącego w twórczości rodzimą muzykę z wpływami obcymi. W latach 80. jego popularność przekraczała granice rodzinnego kraju – artysta zaczął być znany w takich krajach jak: Izrael, Grecja, Portugalia, Francja czy byłe kolonie portugalskie w Afryce. Dzięki płycie O Estrangeiro zaczął być znany również w USA. Sukcesom artystycznym Veloso nie towarzyszyły sukcesy w życiu prywatnym – w 1982 nawiązał bliższą znajomość z 13-letnią Paulą Lavigne. W 1983 rozwiódł się z Dedé, a w 1986 ożenił z Lavigne, wówczas 17-latką; urodziło im się dwóch synów: Zeca (1992) i Tom (1997). To małżeństwo również zakończyło się rozwodem (w 2004).