[6] Lennon's first novel, The Light of Falling Stars (1997), about the aftermath of a plane crash, was the winner of Barnes & Noble's 1997 Discover Great New Writers Award.

His fourth novel, Mailman, was released to critical success in 2003[7] and concerns a mail-carrying protagonist named Albert Lippincott who is clearly losing his mind.

[8] His other books include The Funnies (1999), a comedy about a would-be cartoonist; On the Night Plain (2001), a noir western set in the 1940s; and Pieces for the Left Hand: 100 Anecdotes (2005), a collection of 100 very short stories.

[7] In 2009, Graywolf Press published a new novel, Castle, and reissued Pieces For The Left Hand, which was appearing for the first time in the U.S. His 2008 short story "The Rememberer" is the basis of the CBS television drama Unforgettable.

As a solo artist, recording as Inverse Room, he has released three full-length CDs, Simulacrum (2002), Pieces for the Left Hand (2005) (a companion to the book of the same title), and American Recluse (2007).