Das englischsprachige Lied wurde vom Interpreten selbst, gemeinsam mit John Barry, Leslie Bricusse und Guy Chambers geschrieben beziehungsweise komponiert. Chambers zeichnete darüber hinaus, zusammen mit Steve Power, für die Produktion verantwortlich.[1] Barry und Bricusse sind Co-Urheber, weil das Lied Zitate aus deren Werk You Only Live Twice (Nancy Sinatra) verwendet.[2]
Die Erstveröffentlichung von Millennium erfolgte als Single am 7. September 1998 durch Chrysalis Records. Diese erschien als CD-Maxi-Single mit den B-SeitenAngels (Live), Love Cheat (Demo) und Rome Munich Rome (Demo). Am 26. Oktober 1998 erschien es als Teil von Williams’ zweitem Studioalbum I’ve Been Expecting You.[1]
Das Musikvideo zu Millennium von Vaughan Arnell erhielt 1999 den BRIT Award als British Video of the Year.[3][4] Es zählte bis Juli 2023 über 16 Millionen Aufrufe bei YouTube.[5]