Bandmembers Chris Baird, Nick Cloutman, Jon Baird, and Jason Adams first played together in 1996 under the name Seventeen, releasing two full-lengths and an EP under this name. Bruce Fulford joined the group shortly before the release of their 1999 EP. Legal challenges from Seventeen magazine eventually led the band to change names in 2001; Jon Baird also left the group that same year.
Their first full-length as Lustra was issued in 2003, and soon after the group landed the song "Scotty Doesn't Know" on the soundtrack to the 2004 film EuroTrip. The band also appears briefly in the film, with Matt Damon acting (and lip-synching) as their lead vocalist. The film was not a box office success but sold well on DVD, raising the band's profile long after its theatrical run. "Scotty Doesn't Know" was included on Lustra's 2006 full-length, Left for Dead, and became a hit single that year almost entirely as a result of download sales, eventually peaking at No. 75 on the Billboard Hot 100, No. 39 on the Digital Songs chart, and No. 53 on the Pop 100 in the United States.