Fountains of Wayne was recorded when the band was just a duo, before the recruitment of drummer Brian Young and guitarist Jody Porter to the band, Collingwood and Schlesinger provided all the instrumentation during the recording, except for the bass guitar parts, which were performed by ex-The Belltower bassist Danny Weinkauf. Schlesinger and Porter had also been members of The Belltower, and Weinkauf later played with Lincoln before joining They Might Be Giants. Written over a period of years as outlets to make each other laugh through inside jokes and references to suburban life in New York and New Jersey, the songs on the album were recorded in five days. Dominique Durand of the band Ivy, of which Schlesinger is also a member, provided backing vocals on "Survival Car".
The album's cover photo of a little boy clutching a rabbit and posing like a superhero was shot by Nick Waplington. It was also used for the album cover of Plastic Jewels by the UK band Flamingoes, which came out in the US two weeks before this album.