Millennium was released on May 18, 1999, on which day the Backstreet Boys made a heavily publicized appearance on MTV's Total Request Live.
Millennium blev udgivet den 18. maj 1999, hvor Backstreet Boys samme dag lavede en stærkt publiceret optræden på MTVs Total Request Live Millennium.