This is the song that led to Paul Simon's South Africa visit, where he started recording the tracks for Graceland. In 1984, Simon's friend Heidi Berg gave him a tape of South African recordings called Accordion Jive Hits No. 2, and there was an instrumental song on the tape called "Gumboota" that Simon loved and wanted to record. Not only did he want to record the song, but he wanted to do it with the same South African musicians he heard on the tape: a popular group called The Boyoyo Boys. This turned into a very big deal, since South Africa was under a cultural boycott from the United Nations in protest of their Apartheid policy, so entertainers were strongly discouraged from visiting. Simon went anyway and recorded in Johannesburg with local musicians recruited by South African producers with a connection to Hilton Rosenthal, a white South African who worked for Simon's record company. He recorded the song, retitled "Gumboots," with The Boyoyo Boys, but more significantly, he spent about two weeks there recording with other African musicians, which developed into many of the songs on the Graceland album.
According to Simon, this is the type of music favored by miners and railroad workers in South Africa. The term "Gumboots" refers to the heavy boots worn by these workers while they are on the job.
The lyrics, however, have nothing to do with working in the mines or boots, and the word "Gumboots" never appears. Simon wrote the lyrics for the track when he returned to America - he did his best to weave words around the South African rhythms, and came up three verses connected to the lines, "You don't feel you could love me but I feel you could."
Simon later added soprano and alto saxophones to the song. These instruments are frequently used in "township jive" music ("Mbaqanga"), which is similar to another Simon song, "Diamonds on the Soles of Her Shoes." In fact, these two instruments (and the lyrics) are the only things that make this song different from an already existing South African song that Simon loved.
Paul Simon wasn't thrilled with The Boyoyo Boys when he recorded with them, but he was very happy with some of the other musicians he found. This song stayed on the album only because it led to the Graceland project. Simon told SongTalk: "If it wasn't that 'Gumboots' led me into the whole project, I would have dropped 'Gumboots' from the album. Because I think it's the weakest of the South African cuts."
As he did with all his South African tracks, Simon gave writing credits to the original writers of the song.