Songfacts®:

• This song prepares for the Millennium (year 2000), which was two years away at that time. It was brilliant forethought to create an anthem surrounding the event, and the big chorus with "stars directing our fate" made it the most popular song about the new millennium. This was despite some rather cynical lyrics, where Williams even mentions the "sarcasm in my eyes."
• Williams wrote the song with his producer, former World Party member Guy Chambers. According to Chambers, Williams wrote most of the lyrics very quickly, but didn't have a title for the song. It was Williams who came up with the very topical idea to name it "Millennium." Chambers explained to Songwriting Magazine in June 2019: "There was a lot of talk about the millennium back then, it's a bit like the 'Brexit' word now... not that I'd write a song called 'Brexit.' I just thought it was an interesting word."
• The little bridge in the middle of the song was conceived as a soccer chant. Chambers had the melody for that section written, and Williams came up with the words, "Come and have a go if you think you're hard enough."
• The music for this song is based on Nancy Sinatra's "You Only Live Twice" from the James Bond film of the same name. The actual sample of the song wasn't used because it was a lot cheaper to recreate it in the studio than to clear it, so an orchestra comprising of a 26-piece string section, four French horn players, and a harpist was brought in to record it. Speaking with Sound on Sound, Guy Chambers said: "Robbie came up with the idea for the song. He wanted to use the string section from 'You Only Live Twice,' but put it to a hip-hop beat. Once we had decided that, it was just a matter of finding a beat that worked - something that we eventually achieved by speeding it up."
  
  Chambers added to Songwriting that John Barry, the original composer of "You Only Live Twice," didn't approve of "Millennium": "A few months after it had been released and had been a hit, we actually met John Barry, who wrote that amazing string line, backstage at a prom. We wanted to meet him but he was incredibly unfriendly, I got the feeling that he thought we'd murdered his piece of music. It was a bit awkward to say the least, but I'm still a huge John Barry fan."
• "Millennium" took a mere four hours to write, Chambers told Sound on Sound: "What's interesting is that this is the simplest song Robbie and I have ever written – only two chords. And it's written in D-flat major, which is very unusual in pop music. In all, it took us about four hours to write, but then we always work fast."
• Williams isn't a fan of this song. Speaking with Songwriting, Chambers revealed: "Rob doesn't actually rate this song as one of our best. He doesn't like performing it. He thinks it's one of our 'B' songs rather than one of our 'A' songs. I think it's one of the 'A' songs. That's okay, we can agree to disagree. We don't agree on everything, we never did."
• The music video was directed by Vaughan Arnell and used a James Bond theme to go along with the musical idea. Williams does some very rough recreations of famous scenes from various Bond movies in the clip. The video was filmed at Pinewood Studios in London, home to the famous 007 Stage. British model and television chef Lorraine Pascale stars as one of the Bond girls in the visual.
• Strictly speaking, the new millennium began on January 1, 2001, but it was commonly celebrated a year earlier.
• "Millennium" was the lead single from Williams' second album, I've Been Expecting You. It was Williams' first single to reach #1 on UK chart, knocking All Saints' "Bootie Call" off the top spot. Williams, who was engaged to All Saints member Nicole Appleton at the time, said: "Someone had to be knocked off and it may as well be the wife."
  
  This song also received extensive airplay in the US, where it peaked at #72 on the Billboard Hot 100. Despite this, Williams was never able to truly crack the States. Speaking about his failed bid to win over the country, Williams commented to Billboard in March 2003: "My sense of humor is very British. Maybe my writing is too colloquial. Or perhaps Americans simply don't like me."