1998年5至6月，后街男孩开始筹备《Millennium》的制作、录音工作[3] 。对于这张专辑，他们考虑最多的是音乐质量，因为他们想证明自己的音乐才华。在该专辑中，后街男孩更多地参与了创作，并在音乐中加重了弦乐的成份，这是他们转型的开始：他们想借此突破青春组合只懂劲歌热舞的形象，以求得长远发展[4] 。该专辑的首支单曲《I Want It That Way》由马克斯·马丁创作，由于马克斯·马丁是瑞典人，用的不是母语，所以写出来的歌词没有什么实际意义，只要听起来顺耳就行[1] 。
由于后街男孩想要对粉丝的奉献和鼓励表示感谢，于是就写下一首名为《Larger Than Life》的歌曲，这首歌曲的编曲比较重，布莱恩·T·利特尔于1998年将《Larger Than Life》写完后，便交由制作团队前往瑞典录音，制作人再对词、曲进行修改和补充[1] 。整张专辑的摄影工作由赖希&泰勒负责，蒂姆·伯克比尔、比利·查平、丹尼斯·加洛分别负责鼓、吉他、古典吉他的伴奏，保罗·霍华德则单独负责萨克斯管和打击乐器的伴奏工作，该专辑的艺术指导及设计由杰基·墨菲、尼克·伽马担任[5] 。
从《Millennium》开始，可以明显感觉到后街男孩的音乐风格在不断调整，节奏蓝调的痕迹在后街男孩的身上也越来越浓[6] 。该专辑的制作仍延续上一张专辑的风格，融入了大量的抒情民谣和流行舞曲[7] ，巧妙地融合了两种流派：一种是时髦的美国节奏蓝调音乐，一种是活跃的欧陆流行乐，这是他们在首专时期就已获得的专利，并且直接影响了后一批崛起的男子团体。歌迷也无需担心该专辑中的变化会影响音色，因为《Millennium》几乎是后街男孩前一张专辑的复刻版。《Millennium》中的快板歌曲令人回想起1980年代的迈克尔·杰克逊，而所有的抒情民谣都像是《As Long as You Love Me》的后续作品[8] 。
极富感染力的《I Want It That Way》[9] 、悦耳伤感的抒情曲《Show Me the Meaning of Being Lonely》、后街男孩擅长的舞曲《Larger than life》和《The One》，都是经典之作[7] 。在该专辑的最后一首歌曲《The Perfect Fan》中，五名成员用不同的声音，将这首歌曲的情感演绎的淋漓尽致，歌词描绘了母亲才是一名最完美的歌迷，同时又表达了一个人纵使成功、纵使失败、在母亲那里都是孩子，不管怎样母亲都会包容，这种情感就是母爱。《The Perfect Fan》在后街男孩众多的经典歌曲里并不算出名，歌曲本身很慢、很温柔，没有多加任何一点的修饰，但就是这种温柔才正确地诉说出了一种对于爱的理解[10] 。