The song was written for the 2002 Columbia Pictures action-comedy film Men in Black II, in which Smith portrays Agent J. The song was released as a single from the Men in Black II soundtrack on June 11, 2002. The single reached #77 on the US Billboard Hot 100, but was more successful in the UK, peaking at #3 on the UK Singles Chart. The song features vocals from Trā-Knox, who performs part of the hook in the chorus.
The music video for "Black Suits Comin' (Nod Ya Head)" features footage of Smith performing onstage in a Men in Black II environment, featuring characters and footage from the movie. It is notable that a scene that was deleted from the final cut of the film appears in a montage sequence in the video. The video was directed by Francis Lawrence, produced by Joseph Sassone and first aired on the June 3, 2002 episode of MTV show Making the Video.