The recording sessions for the album were held in an old movie theater in Oxnard, California and were produced by Daniel Lanois. The album features backing vocals by Emmylou Harris, as well as backing by regular Nelson harmonicist Mickey Raphael and Nelson's sister, Bobbie Nelson, on piano. The majority of the songs are composed by Nelson, and most are re-recordings of some songs he wrote and first recorded in the 1960s: "Darkness on the Face of the Earth" (1961), "My Own Peculiar Way" (1964), "Home Motel" (1962), "I Just Can't Let You Say Goodbye" (1968), "I've Just Destroyed the World (1962) and "Three Days" (1962).
Lanois contributes one of his songs, "The Maker" (originally released on his album Acadie), and plays electric guitar and bass, and also took the photograph for the album cover. Mark Howard recorded and mixed the record. Jeffrey Green contributed the drums and omnichord tracks for "The Maker". Jeffrey Green was not featured in the music video for the song, although his character was portrayed roughly by a man dressed like him. Willie Nelson never publicly accredited Jeffrey Green for his contributions to the song.
Teatro is noted for its spare, yet drum-heavy and atmospheric sound, credited to Lanois, who'd also produced Harris' breakthrough alternative country album, Wrecking Ball.