Lisa and Jessica impressed music executive Hayden Bell with their demo tracks and were signed to Excalibur Productions Australia as songwriters in 2004. After being signed to Sydney-based independent record label Engine Room Recordings, they received funding to travel around the world to write and record demos with other songwriters. During this trip, they co-wrote songs that would go on to be released by other artists, including: "What's Going On?" by Casey Donovan, "All About Us" by t.A.T.u. and "Faded" by Kate DeAraugo (also covered by Cascada). By the end of 2004 they travelled to America and signed with Sire Records, a subsidiary of Warner Music for a deal worth $2 million. Taking their name from a line in the film "Heathers" (1988), they called themselves The Veronicas. However the name was also connected to the Archie Comics character Veronica Lodge, leading to the owners suing them for trademark infringement, but resulted in a settlement which included the sisters appearing in the comics.