Recover comprised Dan Keyes (guitar/vocals), Robert Mann (guitar/vocals), Ross Tweedy (bass), and Santiago "Jimmy" Vela (drums). The four first started playing together while in high school, but didn't officially form Recover until 2000. The band recorded a four-song demo in the spring of 2000. The demo found its way to Fueled by Ramen via the band's friends in fellow Austin band The Impossibles. The band would eventually sign with the label and release their debut album, Rodeo & Picasso, in the summer of 2001.

The band toured extensively in support of the album, and in 2002, released a follow-up EP on Fiddler Records, Ceci n'est pas recover. The band continued their exhaustive touring schedule, opening for up-and-coming bands such as Thursday, Taking Back Sunday, and Coheed and Cambria. The band would sign to Universal imprint Strummer Recordings in late 2002 and continue touring throughout 2003. In late 2003, the band retreated to write and record their second full-length with the help of producer and friend Rory Phillips, a process that would take almost eight months. This May Be the Year I Disappear was released in October 2004 to lukewarm reviews. The album marked a significant change in sound, with the band moving away from their signature post-hardcore sound and toward a pop rock sound, polarizing many of the band's fans.

The band embarked on a co-headlining tour with Armor for Sleep and openers Say Anything in early 2005. Later that year, the band announced they were going on an indefinite hiatus, citing Keyes' desire to move to New York and start a new project as the primary reason. On April 30, 2007, the band announced they would be playing their first show in two years for the Everyone Knows Everyone music festival in Austin on June 30, 2007.

In early 2009, the band announced that they have officially reunited and that their first show back will be at the Chain Reaction.