Brand New's second studio album was written in "the year and-a-half or two years" that they were touring the material from Your Favorite Weapon. According to drummer Brian Lane, "Jesse [Lacey] wrote a lot of the lyrics about different things than 'I just broke up with my girlfriend' for the new record." Lacey wrote the songs on an acoustic guitar in his bedroom.
Several of the song titles reference films. The first track entitled "Tautou" references the lead actress, Audrey Tautou, in the movie Amélie. "Okay I Believe You, But My Tommy Gun Don't" is a line from Home Alone 2: Lost in New York and the song "Sic Transit Gloria...Glory Fades" is a line from Wes Anderson's film Rushmore. In addition, the line "and I've seen what happens to the wicked and proud when they decide to try to take on the throne for the crown" (from 'Jaws Theme Swimming') is a reference to a line from the 1999 film Dogma, specifically referencing a line of Matt Damon's character Loki. In their third album, the song "Sowing Seasons" contain the two lines "to bear to hear the truth that you have spoken, twisted up by knaves to make a trap for fools" and "watch the things you gave your life to broken, stoop and build them up with warn out tools." These are taken directly from Rudyard Kipling's poem "If."
Deja Entendu received mostly positive reviews from critics, who praised the band's evolution from their debut album. AllMusic gave Deja Entendu four out of five stars, stating that:
As of 2003, Brand New had sidestepped any notion that they'd be stuck in the prototypical mold found on Your Favorite Weapon. Unlike their debut, Deja Entendu isn't all about bitter breakups and doesn't fall into a permanent punk-pop hole. Produced by Steven Haigler (Pixies, Quicksand), this sophomore effort finds Brand New maturing, reaching for textures and song structures instead of clichés.
IGN rated the album 9.7/10, calling it "probably the best underground release this year."