Millhiser and Frankel both grew up on the Upper West Side of New York City and attended elementary school together. They were later part of a hip hop group called Automato. Automato's debut album was produced by James Murphy and Tim Goldsworthy of DFA. After the release of the album, Automato "kind of fell apart". However, Millhiser and Frankel kept working on music. Initially it was going to be more hip hop work, but decided to create music with vocals and poppier arrangements. The name Holy Ghost! was selected just before the pressing of their debut single "Hold On" in November 2007. The single was described by Resident Advisor as "one of the dirtiest little Italo tunes you're likely to hear this year".
The duo continued to work on various remixes for the likes of Moby, Cut Copy and MGMT. Their second single, "I Will Come Back" was initially released in conjunction with Mountain Dew's Green Label Sound record label. A video was made for the single that is a shot-for-shot remake of New Order's "Confusion" video, including Arthur Baker reprising his role from the original. The song was later included on the Static on the Wire EP, released on the 18 May 2010. The duo also began to play live, starting with a tour with label mates LCD Soundsystem.