En octubre de 1999 publica su nuevo álbum Rainbow que llega al número 2 de las listas estadounidenses. Heartbreaker el primer single junto al rapero Jay Z logra convertirse en su decimocuarto número 1 en Estados Unidos durante 2 semanas. La artista bate el récord de los Beatles al estar en total 60 semanas en el número 1 de la lista de singles, (por 59 de los Beatles, aunque todavía por detrás de Elvis), aunque la canción no fue demasiado radiada, pero si logró las más altas ventas de ese año.