El casete, un tema instrumental llamado "Gumboots-Accordion Jive Hits Number 1", era de una banda sudafricana, The Boyoyo Boys.
En una entrevista, Simon describió la canción de Boyoyo Boys como "música instrumental con un acordeón, guitarra eléctrica, bajo y batería."
[1] Simon más tarde escribió la letra para cantar durante una regrabación de la canción, la cual se convirtió en el cuarto tema del disco, que comienza con la estructura y luego la adición de la melodía.
Graceland ofrece una mezcla ecléctica de estilos musicales como el pop, a capela, isicathamiya, rock y mbaqanga.
El álbum fue fuertemente influenciado por los primeros trabajos de los músicos sudafricanos Johnny Clegg y Sipho Mchunu, y la música pop de su banda Juluka.
Simon incluye agradecimientos a Johnny Clegg, Juluka y el productor de la banda, Hilton Rosenthal en la cita de "agradecimientos especiales" que se incluye en el álbum.
Graceland fue el álbum de Paul Simon con posiciones más altas en los EE. UU.
Se fue tan aclamado por otros críticos que luego anticipó que iba a rematar las encuestas de los críticos Pazz & Jop, publicada por el periódico The Village Voice.
Un popular video musical, protagonizado por Simon y Chevy Chase se hizo para la canción "You Can Call Me Al".
El público era una mezcla multi-racial y muchos espectadores viajaron desde Sudáfrica.
Bonus tracks El grupo Los Lobos aparece en la última pista, "All Around the World or The Myth of Fingerprints" De acuerdo con el saxofonista del Los Lobos Steve Berlin, Simon le robó la canción a Los Lobos, sin darles crédito de composición:[8] No fue un trato agradable para nosotros.
Entonces pasaron seis meses y Graceland se había convertido en un éxito y lo primero de lo que me enteré sobre el problema fue cuando mi manager recibió una carta de un abogado.