According to Pras, the song was originally to be a collaboration between himself and Mya. Ol' Dirty Bastard was in the same building, recording with Sunz of Man and mistakenly burst into the studio where Pras and Mya were setting up, leading Pras to invite him to be a part of the song.
Francis Lawrence directed the video, which features actress Halle Berry and actors Warren Beatty, Oliver Platt, and Joshua Malina. In a play on the theme of the film, which is a prominent white politician acting like a Black American, Bulworth in the music video actually begins to stretch his mouth, pulling his face off to show it's really a mask, and revealing himself to be Pras, who is really the first African-American U.S. president in disguise. Shortly after Pras gets pushed in an elevator, he takes off his suit and performs. Wyclef Jean also appears on the set playing the bass guitar riff at the end of the song. It was nominated for an MTV Video Music Award for Best Rap Video and Best Video from a Film. Another three nominations on the 1998 Billboard Video Music Awards for Best New Artist Clip (Pop), Best New Artist Clip (Rap), and Best New Artist Clip (R&B). It won an 8th Annual MVPA Award in 1999.