There are two versions of the song. The album version contains the lyrics: "So be careful of those killing in Jesus' name/He don't believe in killing at all." The single version that was released to radio replaces those lines with: "And I wish you all a long sightline/And the strength to walk tall." Mellencamp said the record company asked him to provide less controversial lyrics for the version sent out to radio stations to give the song a better chance of getting airplay. "'Walk Tall" was produced by Babyface, who also plays guitar and provides backing vocals on the song.
In 2004, Mellencamp spoke to CMT about his inspiration for writing the song: "'Walk Tall' really was written ... you know, I heard Woody Guthrie say in some kind of documentary that it was important for him to write songs about people and try to make them feel good about themselves. He said, 'I ain't gonna write no more songs that would make anybody feel bad about themselves.' And I always kind of took that with me as a songwriter. I didn't always do that, but in today's world where there seems to be so much ... I don't know ... fear and hatred toward each other, it seemed like, 'If you can write an inspirational song, John, you should probably try to do it,' you know? So that's where that came from. That's how that song was written."
During a concert in July 2006, former vice president Dan Quayle walked out as Mellencamp performed the song after he introduced it as being for "those being ignored by the current administration."