Hed PE had been working on the album since before the release of The D.I.Y. Guys with front man Jared Gomes notifying it through various MySpace posts. Three studio recorded tracks rumored to be on New World Orphans, "War on the Middle Class", "Ordo (ab Chao)", and "Bloodfire", were released via the live CD/DVD combo set, The D.I.Y. Guys on July 8, 2008. The tracks were rough versions of what would later appear on the album.
On November 4, 2008 the band released the music video for "Ordo (ab Chao)" via the band's MySpace. The video showed a different mix than that of the version released on the The D.I.Y. Guys, including new instrumentation such as a melodica during the verses. On November 25, 2008, New World Orphans second single, "Renegade", premiered online on the band's official Facebook account. A video for the song was produced, and premiered on December 20. It was directed by Philip Carrer and Chad Archibald and produced by Lee Hartney of the Smith Street Band for Guelph's premiere film production studio Black Fawn Film alongside film collective Bleeding Apple. Drummer Chris Hendrich appears in the "Renegade" music video with the band.
On November 19, 2008 the official track listing and album artwork were revealed. The album was released in three different color variations of the cover: black, red and white. Each version features exclusive tracks corresponding to their version color. The artwork and final track listing were officially posted via the album's official promotional website.
New World Orphans debuted at 72 on the Billboard 200, their first debut inside 100 since Blackout. The album also peaked no. 5 on the Top Internet albums as well as no. 4 on the Top Independent albums.