1996 was now upon us. "One Sweet Day" was of course still #1 basically everywhere, and the Boyz were actually starting to relax, not thinking about what was going to be next for Boyz II Men. Before they could relax though, they had to attend award shows that nominated them for the later singles from II. II now had sold 16 million copies worldwide, and took the place of Cooleyhighharmony as the biggest selling album by a R&B group ever, and the biggest selling album on Motown Records ever. The first award show they attended is the one that they have won the most awards for, The American Music Awards. They had already won six AMA's before, and in 1996, they were tied with Hootie and the Blowfish for having the most nominations that year with five. They ended up winning two of the five awards that they were nominated for. Those awards were Best Soul/R&B Album (II) and Favorite Duo/Group in Soul/R&B. They did not perform this time, but they did present an award to Brandy, and backstage, they watched her performance, bobbing their heads to her hit, "Baby." Next came the NAACP Image Awards where only Wanya and Shawn showed up to accept their award for Best Group. This of course brought back the break-up rumors. Radio stations were reporting everywhere that their egos had "blown out of proportion" and they could not stand each other. Just like before, those rumors were false. The next award show that they attended in March was one of their biggest accomplishments in a very long while. The award they were given was at the Soul Train Music Awards. The award was the Sammy Davis Jr. Award for Entertainer of the Year. The award was given to them by Bill Cosby, and a short retrospective was shown on them which even moved Nate to tears. The footage showed a very cool Boyz II Men cake from the "Motownphilly" days, them accepting numerous awards, the recording of "On Bended Knee," footage from the video for "Water Runs Dry" and more. The speech was nice, Mike even stepped off of the stage to hug his mom in the audience when Nate was thanking everyone. The award remains a great achievement for the group, who some thought would not even last for long; they sure have proved everyone wrong. The last award they received was in late 1996 at the Billboard Music Awards. The award was a special one for "One Sweet Day" for being the biggest single ever. The Boyz were not there, but Mariah Carey excepted it on their behalf.
Award show season was now over, so the relaxing was about to happen for the fellas. But, they had one more thing to do before they went on about a year vacation. On February 14, 1996, five years after Cooleyhighharmony was released, not only did Boyz II Men appear on the Oprah Winfrey Show for the first time, but they also opened their own label the same day. The label was named Stonecreek Recordings, of course named after their studio. Stonecreek Recordings was distributed by Sony, not Motown Records. This proved to be a huge slap in the face to Motown, after the entire The Remix Collection war. Boyz II Men's goal for the label was to get talent from every corner of the world, and they did fulfill that dream with one artist. The only artist ever released from the label was Uncle Sam, who had one big hit in 1997, "I Don't Ever Want to See You Again" which was a Top 10 hit, and was written by Nate. The label sadly only lasted for about a year and half before Sony cut the label off since only Uncle Sam was the only artist released, which only offered a platinum single and album.
Before the Boyz could relax, they made another appearance at Drexler University in Philly to receive honorary doctorates in around May or June of 1996. A month or so after that, Nate came out with a solo song named "Wishes" which was written by him and Jimmy Jam & Terry Lewis. The video was great for all Nate fans, (it was the only Boyz II Men video released in 1996) and the song was cool also. "Wishes" appeared on the Shaquille O'Neal movie flop, Kazam. It of course marked the third member of Boyz II Men to "leave the Boyz II Men nest" for only one song. The song didn't do as impressive as Wanya & Brandy's "Brokenhearted" or Shawn's "Visions of a Sunset" though. "Wishes" only got to #86 on the Billboard Hot 100 Singles, and got to #56 on the Top R&B Singles Chart.
In August of 1996, Boyz II Men had some controversy, but it all ended up fine in the end. The controversy was a song they sang on the Rhythm of the Games Soundtrack for the 1996 Summer Olympics. The song they sang was not controversial, it was only the "Star Spangled Banner." But, the controversy happened when Boyz II Men submitted the song to the summer Olympics committee to sing it at the Closing Ceremonies of the Olympics, and MTV reported that they called the way they sang the song on the album, "too black." The Olympics spokesmen of course denied the rumor, claiming they actually called the song "too soulful," (whatever that is!). In the end, Boyz II Men submitted a slightly different version of the song, and the song was accepted, and they were now able to sing for America, with millions, maybe billions of people watching all over the world. They were dressed in American flag attire, and sang the song perfectly. A good end to a bad start of a mini-controversy.
By December of 1996, the party was over for Boyz II Men. It was time to go back to the studio and record the much-anticipated third album. While doing this, the Boyz II Bearz, Boyz II Men's own bearz that are dressed like each guy and each sing a song, premiered on QVC, just in time for Christmas. The Boyz II Bearz were a huge success. Selling thousands in one day on QVC, Wanya's bear sold out quickly, Mike's bear came a few months later, and Shawn and Nate's bearz took about a year to sell out, but eventually did.
By early 1997, Boyz II Men's third album was being recorded. 1997 would be an OK year for the fellas, not one of the best of their careers, but it would be ok. In March of 1997, Nate opened his own hair salon in Philly named International Stylings. No, Nate is not cutting hair! Their first public appearance in 1997 was at the opening of the Motown Cafe in Las Vegas, Nevada. A few months prior to that, they had statues made of them for the cafe of them with some of the American Music Awards they had won in the past years. They really were not seen in the public again until July of 1997. They all made appearances in Uncle Sam's debut video, "Can You Feel It," and three out of the four members appeared on Canada's Much Music Da Mix show. Wanya was not there because he was vacationing in Disney World. They talked about their album soon to be released, Evolution. The three members were treating it like a sequel to a movie and like their first album. For the next year, Boyz II Men would have to promote their newest album by themselves, and would end up being the biggest failure of their career.