1999

In januari mergt PolyGram (Motown's distributeur) met Universal. Artiesten en werknemers worden verplaatst of ontslagen, en Boyz II Men kan eindelijk onder het contract met Motown uit. Na 9 jaar Motown sluiten ze een contract met Universal Records.

Op Martin Luther King Jr. Day ontvangen ze de eerste annual Voices of Freedom award in Philly.

Begin 1999 krijgen ze voor album II de RIAA's Diamond Award (er zijn meer dan 10 miljoen stuks van verkocht).

Eind 1999 worden ze door het RIAA Best R&B Group of the Century genoemd.

Ze verschijnen op TV bij de 14e annual Gospel Stellar Awards, Lou Rawl's Parade of Stars en MTV's Ultra Sound: Money for Nothing.

Van het album The Prince of Egypt verschijnt single ‘I Will Get There' (youtube).

2000

Bij Universal verschijnt een verzamelaar op 9 mei: The Ballad Collection

Op 12 september verschijnt weer een ‘echt' album (het vierde studio-album): Nathan Michael Shawn Wanya
Ze hebben voor 't eerst in hun carrière nu meer creatieve invloed op hun eigen albums...

Een clip van het nummer Pass You By verschijnt en een clip van Thank You In Advance.

2001

Universal Records brengt een verzamelaar uit op 30 oktober: Legacy: The Greatest Hits Collection
Zowel in een ‘normale' versie (13 tracks) als in een ‘deluxe edition' (2 cd's, 35 tracks).

2002

Op 11 juni verschijnt het album Full Circle , op het label Arista Records.
Van dit album verschijnt het nummer The Color of Love op 11 juni als single, en het nummer Relax Your Mind op 16 juli als single.

2003

De groep krijgt een nominatie voor een Soul Train Music Award in de categorie R&B/Soul Album Group, Band or Duo, voor het album Full Circle.

Op 7 oktober brengt Motown Records nogmaals een verzamelaar uit (hoezo melkkoe...): 20th Century Masters – The Millennium Collection: The Best of Boyz II Men

Helaas moet Michael McCary afscheid nemen van de groep: hij heeft chronisch last van zijn rug.