As early as February 10, 2001, Manson had made indications that the song would be chosen as the album's third single. The third single was released in physical format, on September 3, 2001, in the UK and, on October 6, 2001, in the US.
A remixed version of the song would later appear in the 2001 Johnny Depp film From Hell. Also, despite its usage of harsh vocals, the band has performed an acoustic version of the song.
The music video for "The Nobodies" was directed by Paul Fedor. It premiered on MTV in June 2001. Technical presentation of the video uses shaking camera techniques, varying perspective shots, closeups, and fast scene shot changes.
Originally, the frontman expressed desire to film the music video in Russia "because the atmosphere, the desolation, the coldness, and the architecture would really suit the song." Another concept called for the incorporation of the MTV stunt and prank reality TV series, Jackass, due to the song's inclusion in the Jackass soundtrack. However, this idea was abandoned after the show began drawing the ire of U.S. SenatorJoseph Lieberman (D-Conn.), who was among the politicians who targeted Marilyn Manson for blame after the Columbine High School massacre. Marilyn Manson explained the idea for the music video:
I already had a story for the video that I wanted to do, a sort of Marilyn Manson fairy tale about some children escaping from an orphanage and seeking refuge with me after fleeing from some terrible, evil nuns who abused them—as all nuns do, I guess. So I decided that they would be watching Jackass on television and the nuns would be upset with them, which is why they'd leave. But now I don't know what they'll be watching [...] Maybe Joseph Lieberman—That might be the most appropriate thing.
— Marilyn Manson, Marilyn Manson: Moral Minority
After the shootings, the media widely reported that listening to Manson's music drove the boys to kill, though in fact they didn't appear to be fans of the band. An interview with him about the Columbine shootings was featured in the 2002 Michael Moore documentary Bowling for Columbine. When Moore asked what he would say to shooters Harris and Klebold, Manson replied, "I wouldn't say anything to them. I would listen to what they have to say and that's what no one did." Also in the film, an acoustic instrumental version of the song is played during a montage of security camera footage and emergency phone calls.
"The Nobodies: 2005 Against All Gods Mix" was released in Europe as the second single and in Asia as an EP in conjunction with Marilyn Manson's Against All Gods world tour, and to radio in the United States in conjunction with the compilation album, Lest We Forget: The Best Of; only the original album version is present on the compilation.