Originally an outtake from the Empire Burlesque sessions titled "New Danville Girl," Dylan re-wrote and re-recorded the song for Knocked Out Loaded as "Brownsville Girl." Ira Ingber, who played guitar on the track, recalled to Uncut magazine: "We started it at Cherokee Studios in those first sessions in late 1984.before we got into the studio, we had practised it during the rehearsal sessions at his house, but we had never played the whole thing up there. When we got to the studio, Bob said he wanted to do it."
"During the recording, Bob said he was short a verse," Ingber added. "I said, 'Let's come back to it tomorrow or whenever you finish it.' He said, 'wait a second.' He took out this impossibly small pen or pencil-like, maybe an inch and half long – and this tiny scrap of paper. He went off into the corner of the studio, and we're waiting maybe five or 10 minutes. He comes back and says, 'OK, let's go.' We start playing the song again, and all of sudden here comes this new verse that he'd written, and it was breathtaking. At that very moment I remember thinking: 'That's why he's Bob Dylan. That's what the guy does. We all looked at each other and we were thinking, well – this is one for the ages."
Dylan wrote the 11-minute epic with Sam Shephard. The playwright accompanied Bob Dylan on the Rolling Thunder Revue of 1975 and co-wrote the surrealist Renaldo and Clara film that emerged from the tour.
In a 2017 interview exclusive to bobdylan.com, Dylan said that "Brownsville Girl" and "In the Garden" were the songs that didn't get the attention they deserved.