Wanting to capture the sound of bands such as the Replacements and the Grifters, he recruited guitarist Tad Kubler (also ex-Lifter Puller), drummer Judd Counsell, and bassist Galen Polivka. Recording mostly live, the band released its debut, Almost Killed Me, on Frenchkiss Records in March 2004. Dave Gardener (Rocket from the Crypt, Drive Like Jehu) and Dean Botulonis signed on to produce Separation Sunday, which arrived in 2005. The World/Inferno Friendship Society's Franz Nicolay (keyboards) and Bobby Drake (drums), formerly of End Transmission and Arm, were also added to the Hold Steady lineup. The band's third effort, 2006's Boys and Girls in America, marked its first release for Vagrant. After writing the majority of their fourth record on the road, the Hold Steady returned to John Agnello's Water Music studio to record Stay Positive, their most heavily produced effort. In July of 2008, the album was released by both Vagrant and Rough Trade.

In 2010 the band announced the departure of Franz Nicolay. Later that same year they released their fifth album, Heaven Is Whenever. In 2012 the band went on a brief hiatus, with frontman Craig Finn releasing his debut solo album, Clear Heart Full Eyes. Regrouping with new guitarist Steve Selvidge in 2013, the revitalized five-piece reentered the studio to record a track for the Game of Thrones soundtrack -- which was also released as a limited-edition single on Record Store Day 2013. Near the beginning of 2014 they announced the release of their sixth album, Teeth Dreams, as well as the covers EP RAGS -- all proceeds from the EP went to help the children of longtime Hold Steady fan Mike "Jersey Mike" Van Jura, who sadly passed away in 2012. After the band finished touring for the album, Finn began work on a solo album. The more intimate and personal Faith in the Future was produced by Josh Kaufman and released by Partisan Records in late 2015. He played solo shows throughout the first half of the year, then turned his attention back to Hold Steady business, namely deluxe reissues of Almost Killed Me and Separation Sunday. They arrived at the end of 2016 and to celebrate, the band (which welcomed back Franz Nicolay) played festivals and a series of sold-out shows in Brooklyn. ~ Kenyon Hopkin & Rich Wilson