Vaux was formed in 1997 in Denver, Colorado, under the original name Eiffel. They released a 7" single themselves, To Write A Symphony, in 1998. Indie label Undecided Records signed the band after they had toured the West Coast extensively for two years, and the band's debut album Audiblenarcotic was released in 2000. The album was a minor success on college radio, and the band earned a spot on the 2001 Warped Tour. In July 2002, for legal reasons, the band had to change its name, deciding on Vaux.

In 2002, Vaux moved to Orange County independent label Volcom Entertainment and released the EP On Life; Living, and the following year, second full-length There Must be Some Way to Stop Them. The album received widespread critical acclaim, prompting Alternative Press magazine to include Vaux in their 100 Bands to Watch feature. During this time, the band embarked upon successful tours supporting Thrice, My Chemical Romance, Coheed & Cambria and The Used.

In January 2004 Vaux signed to major label Atlantic Records. Shortly after, the band released a 5-song EP, Plague Music, on Equal Vision Records. The band's major label debut, Beyond Virtue, Beyond Vice was due for release on November 8th, 2005. However, Vaux recently severed ties with Atlantic. In 2006, the band signed to Outlook Music who will be releasing the album in August 2006.