 By 1998 , Thirty Seconds to Mars was performing gigs at small American venues and clubs . When they first started , lead vocalist Jared Leto did not allow his vocation as a Hollywood actor to be used in promotion of the band . They played their first concerts under different names , before finally settling on the name " Thirty Seconds to Mars " , which was taken from a rare manuscript titled Argus Apocraphex . During this period , the band recorded demo tracks such as " Valhalla " and " Revolution " , or " Jupiter " and " Hero " , which later appeared on the debut album as " Fallen " and " Year Zero " respectively , but also " Buddha for Mary " . Their work led to a number of record labels being interested in signing Thirty Seconds to Mars , which eventually signed to Immortal Records . In 1999 , Virgin Records entered into the contract . 
