The New Amsterdams began as a solo project to then-lead singer for The Get Up Kids, Matt Pryor. In 2000, he released his debut album Never You Mind, which was largely made up of acoustic tracks with sparse accompaniment. However, the album also featured Alex Brahl,Ed Rose, Jake Cardwell & Rob Pope providing extra instrument tracks.
Two years later in January 2002, Pryor released Para Toda Vida, this time sticking almost purely to acoustic guitar, with the exception of a few tracks utilizing harmonica and banjo as well. However, the next year the band went a step further in the release of Worse for the Wear, which utilized a full band for the first time, which at this time included Get Up Kids bandmates Ryan Pope and his brother Rob, as well as longtime friend and producer Ed Rose. The album was one of the earlier albums to be recorded at Black Lodge Studios, the recording studio renovated and co-owned by Ed Rose and the members of The Get Up Kids.
The band's next album, Killed or Cured was released in 2005. However, it was written during a turbulent time within The Get Up Kids leading up to the band's breakup. Because of this Vagrant Records, the label to which both the bands were signed, didn't want to release the album until The Get Up Kids finished their farewell tour in the summer of that year. For this reason, a portion of the album was released online for free via the New Amsterdams website. The album was released in its full version through retail channels on April 10, 2007.
In 2006, the band released the album Story Like a Scar with what is now the current lineup, including Bill Belzer on drums, Eric McCann on upright bass, and Dustin Kinsey on guitar.
In January 2008 the band released a collection of demos and b-sides, available exclusively through their website.
In May of the same year, they went on their first European tour, starting in Amsterdam. The band planned to go into a small hiatus after that due to Matt Pryor's involvement with the Get Up Kids. In a November 2011 interview with MidcoastStation.com, Pryor said he had plans to release a New Amsterdams compilation.