Coming at a time when Simon's musical career was at something of a low ebb following the disappointing public response to Hearts and Bones, the project was originally inspired by Simon's listening to a cassette of the Boyoyo Boys instrumental "Gumboots." In an interview, Simon described the Boyoyo Boys track as "instrumental music with an accordion, electric guitar, bass, and drums." He said it reminded him of "a certain kind of fifties rock 'n' roll." Simon later wrote lyrics to sing over a re-recording of the song, which became the fourth track on the album, beginning with the structure and then adding the melody.
Graceland features an eclectic mixture of musical styles including pop, a cappella, isicathamiya, rock, and mbaqanga. The album was strongly influenced by the earlier work of South African musicians Johnny Clegg and Sipho Mchunu, and the Zulu-Western pop cross-over music realized in their band Juluka. Juluka was South Africa's first integrated pop band. Simon includes thanks to Johnny Clegg, Juluka and Juluka's producer Hilton Rosenthal in the "Special Thanks" citation included in Graceland's liner notes. Much of the album was recorded in South Africa, and it features many South African musicians and groups. Simon faced accusations by organisations such as Artists United Against Apartheid, anti-apartheid musicians including Billy Bragg, Paul Weller and Jerry Dammers and the then GhanaianAmbassador to the United NationsJames Victor Gbeho that he had broken the cultural boycott imposed by the rest of the world against the apartheid regime in South Africa, which was in its final years at the time. Although supported by the United Nations Anti-Apartheid Committee, as the album showcased the talents of the black South African musicians while offering no support to the South African government, even the ANC protested the collaboration as a break in the cultural boycott. However Simon also received praise for encouraging South African music from Hugh Masekela, one of South Africa's most prominent musicians and an exiled opponent of apartheid, who subsequently toured alongside Simon and Miriam Makeba. The worldwide success of the album introduced some of the musicians, especially the vocal group Ladysmith Black Mambazo, to global audiences of their own. The song Homeless was written jointly by Paul Simon and Joseph Tshabalala, the lead singer of Ladysmith Black Mambazo, to a melody from a traditional Zulu wedding song.
The group Los Lobos appear on the last track, "All Around the World or The Myth of Fingerprints." According to Los Lobos's saxophone player Steve Berlin, Simon stole the song from Los Lobos, giving them no songwriting credit:
"It was not a pleasant deal for us. I mean he [Simon] quite literally—and in no way do I exaggerate when I say—he stole the songs from us... We go into the studio, and he had quite literally nothing. I mean, he had no ideas, no concepts, and said, 'Well, let's just jam.' ...Paul goes, 'Hey, what's that?' We start playing what we have of it, and it is exactly what you hear on the record. So we're like, 'Oh, ok. We'll share this song.' ...A few months later, the record comes out and says 'Words and Music by Paul Simon.' We were like, 'What the fuck is this?' We tried calling him, and we can't find him. Weeks go by and our managers can't find him. We finally track him down and ask him about our song, and he goes, 'Sue me. See what happens.'" 
Paul Simon answered:
"I just said at this stage I don't care whether the album comes out without Los Lobos on it. I was getting really tired of it—I don't want to get into a public slanging match over this, but this thing keeps coming up. So we finished the recordings. And three months passed, and there was no mention of 'joint writing.' The album came out and we heard nothing. Then six months passed and Graceland had become a hit and the first thing I heard about the problem was when my manager got a lawyer's letter. I was shocked. They sent this thing to my manager, not me. If there was a problem, they could have contacted me direct. They've got my home number; we talked a lot. If you ask me, it was a lawyer's idea. You know, 'The record's a hit, and there's $100,000 in it.' They had nine months from the recordings to talk to me about all this, but I heard nothing. And it's still not sorted out, because they still keep bringing it up—I heard they'd done this interview for you. I don't want to get into a public slanging match with them, because I really like their music." 
Graceland was Paul Simon's highest charting album in the U.S. in over a decade, reaching #3 in the national Billboard charts, receiving a certification of 5× Platinum by the RIAA and eventually selling over 14 million copies, making it Simon's most commercially successful album. Critics welcomed its eclectic mix of sounds and broad, quirky subject matter and it regularly shows up in critic polls and "recommended" lists. The album also helped to draw worldwide attention to the music of South Africa.
The album drew accolades from the beginning. Rolling Stone called it "lovely, daring and accomplished" and Robert Christgau enthused it was "so strange, so sweet, so willful, so radically incongruous and plainly beautiful." It was so acclaimed by other critics that he later anticipated that it would top The Village VoicePazz & Jop critics poll for that year (1986).
"I don't like the idea that people who aren't adolescents make records. Adolescents make the best records. Except for Paul Simon. Except for Graceland. He's hit a new plateau there, but he's writing to his own age group. Graceland is something new. That song to his son is just as good as 'Blue Suede Shoes': 'Before you were born dude when life was great.' That's just as good as 'Blue Suede Shoes,' and that is a new dimension."
In the GracelandClassic Albums video, Simon states that he considers the title track the best song he has ever written. A popular music video starring Simon and Chevy Chase was made for the hit song "You Can Call Me Al". Simon toured the album extensively, featuring many of the artists from the album in addition to exiled South Africans Hugh Masekela and Miriam Makeba. Two concerts in Harare, Zimbabwe, were filmed in 1987 for release as "The African Concert". The audience was a multi-racial mix with many travelling from South Africa.
The success of the album earned Paul Simon the Best International Solo Artist award at The Brit Awards in 1987.
In 1998, Q magazine readers voted it the 56th greatest album of all time. In 2006, Q magazine placed the album at #39 in its list of "40 Best Albums of the '80s".
It was also ranked #84 in a 2005 survey held by British television's Channel 4 to determine the 100 greatest albums of all time.
In 1989, it was rated #5 on Rolling Stone magazine's list of the 100 Best Albums of the Eighties.
It was placed 81st (71st in the updated version from 2012) on the list of Rolling Stone magazine's 500 Greatest Albums of All Time as "an album about isolation and redemption that transcended "world music" to become the whole world's soundtrack."
According to AcclaimedMusic.netGraceland is ranked at #78 on the greatest albums of all time. It is also ranked #15 for albums released in the 1980s, and it is the second-highest ranking album of 1986, behind The Smiths' The Queen Is Dead).
In 2002, Pitchfork named it the 85th best album of the 1980s citing it as "a phenomenal musical achievement".
In 2006, Time named it one of the All-Time 100 Albums.
In 2012, Slant Magazine listed the album at #19 on its list of "Best Albums of the 1980s".
A 2012 documentary film, Under African Skies, directed by Joe Berlinger celebrates the 25th anniversary of the album's release, and includes archival footage, interviews, discussion of the controversy associated with the original release, and coverage of an anniversary reunion concert.
In 2012, American Songwriter gave the 25th anniversary re-issue 5 stars, describing the album as "a cultural experiment that changed the way the western world viewed South Africa."
In 2012 the 25th Anniversary edition of the album entered the UK top 10 once again.
^Geoff Hill The Battle for Zimbabwe: The Final Countdown 2003 - Page 211 "The song was written jointly by Paul Simon and Joseph Tshabalala, the lead singer of Ladysmith Black Mambazo, and the melody is from an old Zulu wedding song: We are homeless, we are homeless . . . Somebody cry, why, why, why?"