W tym samym roku nagrał piosenkę „Mi primera canción” ze swoim idolem Paco de Lucią. Z trzecim oficjalnym albumem studyjnym zatytułowanym po prostu 3 w roku 1996 przyszła próba zaistnienia na światowych listach przebojów. Płyta została nagrana także w portugalskiej i włoskiej wersji językowej, a singiel „La fuerza del corazon” zajął 9. miejsce na liście US Latin Pop.
Maestro Mas, płyta z silnymi wpływami flamenco i gorących rytmów uzyskała w samej Hiszpanii status 22-krotnej platynowej, natomiast pochodząca z niej piosenka „Corazon partio” jest uważana za absolutnego klasyka i punkt zwrotny w jego karierze; jej cover wykonuje m.in. Julio Iglesias. Dzięki temu sukcesowi artysta po raz pierwszy wyruszył w trasę po Stanach Zjednoczonych. Ogromna sprzedaż albumów Más z 1997 roku i El Alma Al Aire z 2000 r. uplasowała go w grupie artystów o największej liczbie sprzedanych płyt na świecieAlejandro Sanz na lastfm.pl.. El Alma Al Aire, pierwsza bardziej eksperymentalna płyta Sanza, przekroczyła w pierwszym tygodniu sprzedaży w Hiszpanii milion kopii, czym artysta pobił swój własny rekord ustanowiony poprzednim albumem. Płyta przyniosła mu cztery Latin Grammy Awards 2001, m.in.