The tune's success surprised McGraw. "'Indian Outlaw' was sort of this novelty, weird-sounding song," McGraw recalled at a media event in 2016. "I moved to town in May, early May, of 1989; the same day Keith Whitley died was the day I moved to town. That night … I met [songwriter] Tommy Barnes... We sat up in a hotel room, and he played me 'Indian Outlaw' that night, the first night I moved to town, and I told him I was going to record that song."
"It took me a while to get to it," McGraw continued. "I played that song in clubs forever, and it was just so different. I didn't know how people were going to take it. I didn't know it was going to work."