The Book of Knots was formed in 2003 by three core band members Joel Hamilton, Matthias Bossi and Tony Maimone at Hamilton and Maimone’s Brooklyn based Studio G. Members of Book of Knots have played or worked with various acts previously, including Skeleton Key, Sleepytime Gorilla Museum, Shiner, Battle of Mice, Sparklehorse, Elvis Costello, Unsane, Pere Ubu, Frank Black, They Might Be Giants and more. Carla Kihlstedt (of Tin Hat Trio, Sleepytime Gorilla Museum, 2 Foot Yard among others) joined later in 2003 to solidify what would become the group's core quartet.
Together, the Book of Knots decided to release three conceptual records: their first was to be an ode to rotting seaside towns, a self-titled debut which appeared on Arclight Records in 2004. Second would be a tribute to the American rust belt, titled Traineater, the group was signed to Anti- in November 2006, with the album's release following in April 2007 and featuring guest spots from the likes of Tom Waits, Mike Watt, Jon Langford and David Thomas. Third, devoted to all things aeronautical, was Garden of Fainting Stars, the title track being written and performed by Elyas Khan of Nervous Cabaret. It was released on Ipecac Recordings June 14, 2011 and featured Mike Patton, Blixa Bargeld and more.