Kolejną płytę "Never Say Never" wydała w 1998 roku. Album bardzo szybko otrzymał status platynowego w USA. W 1998 roku "Never Say Never" stał się również platynowym w Kanadzie, Japonii, Australii, Nowej Zelandii i Południowej Afryce. W efekcie, na świecie sprzedano ponad 9 milionów kopii tej płyty.
W 1999 roku artystka rozpoczęła swoje pierwsze światowe tournee. Odwiedziła wtedy kraje Europy Zachodniej i Japonię. Warto wspomnieć, że w 1995 roku towarzyszyła grupie Boyz II Men w ich amerykańskiej trasie.
Dwie pierwsze płyty wokalistki nominowano do nagrody Grammy, a sześć singli znalazło się w Top Ten amerykańskiej listy przebojów (m.in. "Baby" i "Sittin' Up In My Room"). Brandy zagrała także w filmie "I Know What You Did Last Summer Part 2", u boku Jennifer Love Hewitt.
"Full Moon" to trzeci album w dorobku wokalistki. Powstał przy współpracy słynnego producenta Rodney'a Jerkinsa (Michael Jackson, Jennifer Lopez, Spice Girls) i kilku specjalistów od dobrych brzmień, takich jak Warren Campbell (Angie Stone, Sisquo) i Keith Crouch (Toni Braxton, Boyz II Men). Brandy twierdzi, iż "Full Moon" to jej najbardziej osobista płyta. Pilotował ją singiel "What About Us?".
W czerwcu 2004 roku ukazał się kolejny album, zatytułowany "Afrodisiac" - pierwsza płyta wokalistki od czasu platynowego krążka "Full Moon" z 2002 roku. Producentem albumu Brandy, poza jednym utworem, został słynny Timbaland. "Afrodisiac" to spora dawka ciepłej, soulowej muzyki. Na pierwszym singlu ukazał się utwór "Talk About Love", w którym gościnnie śpiewa Kanye West.
W kwietniu 2005 roku ukazała się składanka z największymi przebojami wokalistki. Wśród 18 piosenek, obok numerów znanych z studyjnych albumów, znalazły się także utwory ze ścieżek dźwiękowych do filmów (nagrane z Tamią, Gladys Knight i Chaką Khan "Missing You" z "Desperatek" i "Sittin' Up In My Room" z "Czekając na miłość") i różnych składanek (duet z Ray'em J "Another Day In Paradise" z płyty "Urban Renewal", która była hołdem dla Phila Collinsa). "The Best Of Brandy" zamyka utwór "Rock With You", z repertuaru Michaela Jacksona, nagrany z Quincy Jonesem i Heavy D. Wśród znanych gości możemy usłyszeć także Kanye Westa ("Talk About Our Love") oraz Queen Latifah, Yoyo i MC Lyte (remiks debiutanckiego singla "I Wanna Be Down" z 1994 roku).
Kanye West • Timbaland • Boyz II Men • Michael Jackson • Jennifer Lopez • Spice Girls • Angie Stone • Toni Braxton • Chaka Khan • Phil Collins • Quincy Jones • MC Lyte • JoJo • Christina Milian • SoShy • Diddy • Cee-Lo Green