Where do you start with something like Paul Simon’s Graceland? It is one of those huge, revered albums that possess a real legacy, a veteran of countless ‘best of’ lists and a genuine musical landmark. Its twenty-fifth anniversary sees it released in a handsome CD/DVD package accompanied by Joe Berlinger’s Under African Skies, a new documentary concerning itself with the making of the album and the controversy it quickly provoked, via Simon’s reconnecting with many of his players (and critics) as he journeys back to South Africa. It is a fascinating film, but the album is the real star here, sounding as fresh, vital and universally accessible as ever 25 years down the line.

Rummaging through my parents’ cassettes as a young child provided my introduction to Paul Simon through Simon and Garfunkel, and my abiding memory of listening to them at that age is one of warmth and easy melody. I wasn’t, I remember, too impressed with ‘Bridge Over Troubled Water’ (finding it a touch overblown even then), but in general I loved the pair’s songs, though they were soon cast aside in favour of other, more modern obsessions. It took me a while to catch up to Graceland, but when I finally did it was a pleasure to discover that that warmth and melody from Simon’s earlier recordings not only remained, but if anything was amplified here. Despite being born out of a troubled nation and finding its maker at something of a career low point, Graceland never sounds anything less than completely assured, confident in its flourishes and utterly its own beast.

Simply put, its fusion of South African styles with Simon’s ear for a melody and memorable lyric resulted in a masterclass of modern pop music. As detailed in the liner notes, Simon was inspired to record in South Africa after a friend gave him a cassette entitled Gumboots: Accordion Jive Hits, Volume II. Unaware of the performers involved or its country of origin, he was drawn in by its joyful quality, something he considered both 'familiar and foreign-sounding at the same time.' Upon discovering he was listening to Mbaqanga, a form of street music from Soweto, South Africa, he was put in touch with a Johannesburg-based producer and soon flew out to the city to begin sessions for what would later become his defining work. Of course, in doing so he violated the international cultural boycott of apartheid-era South Africa, something Berlinger’s documentary is at pains to address. It was a bold move – and perhaps not the most advisable one, in all honesty – but the South African black musicians’ union welcomed him nonetheless (if not the African National Congress), and thus the legend and controversy surrounding Graceland began.

One of the many remarkable things about the record is how it was put together. Simon arrived in Johannesburg with the intention of recording rhythm tracks first, lyrics second. Sessions in London, New York and Los Angeles followed, a host of African musicians featuring in the writing and recording process, from names like South Africa’s Ladysmith Black Mambazo, the Boyoyo Boys (the ‘Gumboots’ group Simon initially heard on that cassette) and guitarist Ray Phiri’s band Stimela to Senegal’s Youssou N’Dour. In Under African Skies, recording engineer Roy Halee discusses how overwhelming it was to take all the material Simon had assembled and turn it into something cohesive, and what diligence it took on Simon’s part to turn these loose, spirited recordings into actual songs.

But what songs they are, and how well they have aged. In his introductory liner notes, writer Jesse Kornbluth contends that Graceland is 'that rarest of albums: a popular masterpiece that reveals something new with each hearing.' He is not wrong. These 11 songs are each little wonders of their own. From the wistful ‘Graceland’ itself (Simon’s favourite) to the gentle, refined beauty of tunes like Ladysmith Black Mambazo collaborations ‘Homeless’ and ‘Diamonds on the Soles of Her Shoes’, the LP is a treat throughout, its heady amalgamation of styles and rhythms not once too clinical, too studied or too dense. In terms of musicianship, fretless bass-player Bakithi Kumalo is surely to be credited with its title track’s soft, insistent pulse, he and Ray Phiri also combining wonderfully on the likes of ‘Crazy Love, Vol. II’ and perhaps the album’s most recognisable cut, ‘You Can Call Me Al’.

There are moments here, like on the third verse of ‘Crazy Love’, when Simon’s voice glides into an unexpected, effortless falsetto, or as ‘Under African Skies’ dissolves into washes of sound and lightly ringing percussion, when Graceland sounds transcendent. There are others, like on the interlocking guitar and bass groove of ‘I Know What I Know’ or that same song’s vocal turn by General Shirinda and the Gaza Sisters when it just sounds vibrant and alive, impervious to any wider concerns or political firestorms. Simon’s lyrics are perceptive and ranging throughout, his vocals lilting and unforced; whether offering impressionistic scenes or deft character sketches, these songs are replete with memorable lines, instances and emotions. In the documentary he speaks of how liberating it was to be left alone by his label in the wake of 1983’s underperforming Hearts and Bones. On first song ‘The Boy in the Bubble’, he evokes the arrival of the Information Age, “days of miracle and wonder”, with appropriate levels of awe and uncertainty, his lens always trained on the underlying human aspect, where it remains across the set.

It is difficult, mind, to wholly divorce Graceland from the struggles of apartheid-era South Africa, and this is what Berlinger’s film zones in on. The framing device is a conversation that took place in South Africa last year between Simon and Dali Tambo (founder of Artists Against Apartheid and one of his fiercest critics), where both parties agree to 'tell their story,' against myriad archival and recent footage. The film does well to neither wholly excuse nor justify Simon’s contravening of the cultural boycott. If it does, ultimately, come down on the side of the musician, that is to be expected – this is a celebration of the record, after all – but several interesting points are raised over its running time, and from Simon’s initial reaction to the furore ('I was invited there,' he insists during a press conference in 1986, 'invited by black musicians') through to his admission that there is 'a lot [from the South African side of things] I still don’t know,' it is clear how much the allegations of harming the anti-apartheid cause wounded him. In one of the film’s more affecting moments, he describes the thrilling atmosphere in the studio, reiterates that the musicians welcomed him and points out that their relationship was primarily musical before blossoming into enduring friendship, before Tambo gently reminds him that 'these were not free people, Paul.'

In spite of diving headlong into this argument, the film also does a fine job of exploring the impact and legacy of of the album: Vampire Weekend pop up early on to pay tribute, and thoughtful words from the likes of Philip Glass, David Byrne and Harry Belafonte are interspersed throughout. Less essential, but intriguing nonetheless, are contributions from Oprah Winfrey and Whoopi Goldberg, but the real fun here lies in seeing Simon reunite with the musicians that made the record possible in the first place. From the exuberant Joseph Shabalala of Ladysmith Black Bambazo and enigmatic piano-accordion player Forere Motloheloa to the guitar, bass and drums unit of Ray Phiri, Bakithi Kumalo and Isaac Mtshali respectively, hearing the story of the record from the players themselves – and the bemusement with which they greeted Simon to begin with – is valuable, engaging stuff, a must for any fan. If another controversy regarding the album is conspicuous by its absence (that of the disputed songwriting credit on ‘All Around the World or The Myth of Fingerprints’ with East L.A.’s Los Lobos), it is perhaps understandable given how this chronicles the album in terms of South Africa, something that episode doesn’t really figure into.

The set also features a few demos and odds and ends, the picks of the crop being the previously available early rendering of ‘Homeless’, and Simon discussing exactly how the song ‘Graceland’ came to be recorded as the last track of the audio CD. The music videos included on the DVD make for endearing callbacks – dated in a way the music never will be – but the 1986 Saturday Night Live performance of ‘Diamonds on the Soles of Her Shoes’ is as blissful now as I can only imagine it felt at the time.

So, where do you start with something like Paul Simon’s Graceland? The short answer is probably right here.