Originally consisting of Ray (bass/vocals), Brandon (drums) , and Zach Doe (guitar), the band released their debut EP A Bomb on a Laramie communal label, One Legged Pup, in 2002. Soon after, Doe left and went back to Chicago, leaving the twins without a guitarist until they found University of Wyoming Music Major Joel Pattinson. In 2003 they wrote and recorded their first full length LP Another Way, also released on One Legged Pup. The release was vinyl only (the first 500 on pink vinyl), released on Halloween night 2003. The band continued to play and promote numerous local shows, even landing some opening spots in Laramie with All and The Ataris. The band was to embark on a short summer tour of the midwest in 2004. When Pattinson couldn't make the trip due to his obligations to the University Orchestra, the Carlisles called up their old friend Kody to play guitar on the tour. The tour went well, and they ended up playing some of the new songs that Kody had written, and by the end of the tour, he was a permanent member of the band.

In late 2004 and early 2005 the band recorded their Red Scare debut full length, Total which contains dual vocals from Ray and Kody. After Total was released, the Groovie Ghoulies took notice of the band, and offered them a spot on their Space Stationstage at the Vans Warped Tour. Soon after, the Ghoulies decided to drop Warped Tour, and embark with Bottlerocket, and The Teenage Harlets on the Teen Kicks Tour 2005. They would go on to play shows with The Methadones, Chixdiggit, and The Mr. T Experience. In the summer of 2006, Bottlerocket embarked on another nationwide tour, this time with Fat Wreck Chords new wave act, the Epoxies.