The record builds on his previous work in that it is largely bluegrass and newgrass inspired. Although Not All Who Wander Are Lost was Thile's third solo album, it is widely considered his first major one, primarily based on the fact that Nickel Creek's initial success came in 2000 with their platinum debut album.
The title of the song "Riddles in the Dark" is also rooted in the works of Tolkien. It is the title of one of the chapters of The Hobbit, the chapter in which Bilbo and Gollum compete in a contest of riddles.
The title of the song "Club G.R.O.S.S." comes from the Calvin & Hobbes comic strip. The club was started by Calvin and his stuffed tiger, and stands for "Get Rid of Slimy GirlS."