In 1984 stelde Simon vast dat zijn album Hearts and Bones, zijn zesde soloalbum in een productie van Russ Titelman, Roy Halee en Lenny Waronkel, niet goed verkocht had. Ook de twee singles daaruit Allergies en Think too Much werden geen hoogvliegers. Muzikaal zat Simon op een dood spoor Net dan krijgt hij van een vriend een cassette met daarop muziek die je in de straten van Soweto op elke hoek kan horen. Zuid-Afrikaanse muziek in een aanstekelijk ritme. Ginder noemen ze dat genre mbaqanga: een mengeling van jazz, marabi en kwela, gemakkelijke volkse deuntjes die op eenvoudige en goedkope instrumenten worden gespeeld, zoals zelfgemaakte fluitjes. De muziek die Paul Simon op die cassette te horen krijgt, staat verzameld op het album Gumboots: accordeon jive hits, volume II. Op zijn album Graceland heeft Simon trouwens een volledige track gewijd aan Gumboots. Het is zeer vrolijke en aanstekelijke muziek uit een tijdperk dat van wereldmuziek nauwelijks sprake was. De enige Zuid-Afrikaanse hits die tot bij ons waren geraakt, waren sommige songs van Hugh Masakela en Myriam Makeba. De Zuid-Afrikaanse liedjes die Paul Simon te horen krijgt op die cassette worden uitgevoerd door The Boyoyo Boys. Hij had thuis al scattend met hun stemmen op de achtergrond een aantal liedjes uitgeprobeerd en wou hen contacteren om samen met hen in hun thuisland wat nummers in the blikken. Simon stond er toen niet bij stil dat op basis van de apartheid die in Zuid-Afrika heerste, er op dat moment een internationale culturele boycot werd gevoerd. Via zijn platenfirma geraakt hij in contact met Hilton Rosenthal, een muziekproducer die hem een hele rist Zuid-Afrikaanse platen laat beluisteren. Simon negeert, een beetje onwetend, beweert hij achteraf, de culturele boycot, vraagt aan Rosenthal een aantal muzikanten op te trommelen en nog geen jaar later zit hij in de studio in Johannesburg om een aantal nieuwe songs in te blikken. De muzikanten die hij daar heeft aangetrokken zijn: Tao Ea Matsekha, een groep uit Lesotho, General M.D. Shiranda and The Gaza Sisters en The Boyoyo Boys Band. Maar de fusie tussen zijn liedjes en hun Zuid-Afrikaanse ritmen vlot moeilijker dan Simon aanvankelijk dacht. De samensmelting lukt niet zo goed. Via urenlange jamsessies komen ze uiteindelijk tot een soort aanvaardbare mix van beide werelden. Voor Simon is het erg moeilijk om datgene dat hij wil horen te omschrijven, want zijn muzikanten praten nauwelijks Engels. Nu is de sfeer ook niet meteen je dat. In Zuid-Afrika was het niet de gewoonte dat blanke en zwarte muzikanten met elkaar vlot omgingen, schouderklopjes uitdeelden, samen aan tafel zaten enz… De sfeer was beladen, er hing een onaangename spanning in de lucht. In 1985, wanneer Paul Simon druk bezig is met de opnamen van Graceland, staat het apartheidsregime volop in de belangstelling. Vergeten we niet dat Nelson Mandela, de voormalige leider van het ANC, het Afrikaanse Nationaal Congres, nog in de gevangenis zit en dat de blanke Frederik Willem De Klerk als president de plak zwaait. Met geweld wordt de zwarte meerderheid de kop ingedrukt. Simon ziet hoe het racisme in Zuid-Afrika nog altijd hoogtij viert. Hij houdt die ondraaglijke sfeer niet vol en verhuist met de ganse ploeg naar de opnamestudio in New York. In Zuid-Afrika heeft Paul Simon intussen wel al zes nummers voor zijn album klaar. Hij was anders te werk gegaan dan normaal. Deze keer kwam hij niet naar de studio met kant en klare teksten. Ook geen melodie zat er in zijn hoofd. Hij wilde eerst vertrouwd geraken met de verschillende ritmen, die ook eerst inblikken en pas dan zou hij er een tekst bij schrijven en inzingen.
Eenmaal in New York gearriveerd, zijn de Zuid-Afrikaanse muzikanten dol van blijdschap. Ze voelen zich verlost, vrij en gewaardeerd als zwarten. Er wordt verder gewerkt in The Hit Factory in New York City. Paul Simon viert zijn muzikale teugels en trekt naar Lafayette, Louisiana om daar samen met enkele zydeco muzikanten enkele fragmenten in te blikken. Hetzelfde doet hij in Los Angeles samen met Los Lobos. Die werkten mee aan het nummer All Around the World of The Myth of Fingerprints. Maanden nadat het album een immens succes te beurt is gevallen, claimen Los Lobos een deel van de auteursrechten van de song. Tot op de dag van vandaag is die kwestie nog altijd niet opgelost ook al houden ze vol dat toen Simon in de studio arriveerde er niets op papier stond en dat zij hem aan de melodielijn en een deel van de lyrics hebben geholpen. Voor de song Diamonds on the Soles of Her Shoes doet Simon een beroep op Ladysmith Black Mambazo onder leiding van Joseph Shabalala en de Senegalees Youssou N’Dour op percussie.Ladysmith Black Manbazo werd in het begin van de jaren zestig opgericht door Josephen leende veel van de muziektraditie en songs van de Zulu’s. Pas in 1973 namen ze hun eerste plaat op. Zij werden toen al gerekend tot de beste Zuid-Afrikaanse a-capellagroep.
Het album Graceland wordt wél een fenomenaal succes. Wereldwijd een regelrechte hit. Met zijn album toonde Paul Simon dat Afrika stond voor veel méér dan armoede en ellende. Toch oogstte hij kritiek omdat men vond dat hij door de door de ANC uitgeroepen culturele boycot naast zich neer te leggen niet had meegeholpen aan het uitroeien van het apartheidsregime. Tijdens betogingen wordt er letterlijk ‘Yankee Go Home’ in zijn richting gescandeerd. Ook al had hij de Zuid-Afrikaanse muziek een mooi klank- en uithangbord gegeven op zijn album Graceland, toch vonden de aanhangers van het ANC niet dat hij hun daarmee ook maar één stap had verder geholpen. Het zat hun hoog dat hij vooraf geen afspraken had gemaakt met de vrijheidsbeweging. Zij vonden dat Simon door in Zuid-Afrika te komen musiceren en opnemen, akkoord ging met president De Klerk en zijn regering. Op basis van hun apartheidspolitiek werden blanken en zwarten nog altijd van elkaar gescheiden, er werd op het zwarte ras laatdunkend neergekeken. Op het moment dat Graceland in 1985 in de hitlijsten opduikt, woedt de strijd op zijn hevigst. Hoe vreemd het ook in onze oren mag klinken, het ANC had liever gehad dat Simon niet met Zuid-Afrikaanse muzikanten had samengewerkt.
