For most of us Cabaret means Bob Fosse's great film, with Liza Minnelli at her most divinely decadent and Joel Grey revealing the creepiest smile in show business as the Master of Ceremonies. It made a huge impression on me as a teenager, and for several months I spent a lot of time fantasising that I was the movie's English hero, Michael York, and that safe suburban Surbiton was really dangerous, glamorous Berlin between the wars.

I therefore approached the revival of Kander and Ebb's original stage show at the Donmar Warehouse with some trepidation, fearing it couldn't possibly live up to cherished nostalgic memories. I was wrong. Cabaret is a very different experience on stage, but an even more compelling one, and the show's two superb young stars, Alan Cumming as the MC and Jane Horrocks as the lovable and infuriating Sally Bowles, triumphantly stamp their roles in their own image.

Director Sam Mendes has removed the stalls seats from the Donmar Warehouse and set up cabaret tables instead, turning this fine small theatre into the Kit-Kat Club. It is a place of wonderfully alluring sleaze. The band, both chaps and girls, are dressed in scanty black underwear and blow up a storm, the chorus girls look as though they have been knocking around for years, and Cumming presides over the proceedings like a sinister Mephistopheles.

There is little of Joel Grey's sophistication. This MC looks like a former rent boy and he has a whore's corrupt smile of complicity. He rubs his genitals and thrusts them provocatively at people sitting in the front row, he bares his bum to reveal a swastika, and he carries with him a whiff of real evil. Cumming is an undoubted star, putting over great songs like Money and If You Could See Her with real panache, even as he conjures up the bilious ambiguous spirit of the piece. And, like all true stars, it is impossible to take your eyes off him whenever he is on stage. He prowls it like a beast of prey, as if it were his natural territory.

Different but just as compelling
 Jane Horrocks as Sally Bowles in Cabaret

Jane Horrocks, very wisely, offers a Sally Bowles who has absolutely nothing in common with Liza Minnelli's version. A frail blonde waif, she speaks with a cut-glass English accent eerily reminiscent of Celia Johnson, giving the impression that her character has only recently left a posh girl's boarding school. This Sally's sinful sophistication is only the thinnest of veneers and when she performs the wonderfully sexy Mein Herr; sucking a lollipop inscribed with the words Ich Liebe Dich, you seem to be in the presence of a Lolita-like nymphet. No wonder the engaging Adam Godley falls for her charms. Her performance is at its most devastating in the closing moments. Liza Minnelli turned the title number into a defiant song of triumph. But as Horrocks reaches the final declaration that "Life is a cabaret" her face crumples and the line becomes a shriek of terror and disgust.

Mendes's production leads a smiling audience into a world of horror. He has sensibly refused to overdo the Nazi threat in the opening scenes, so that when you catch sight of the first swastika it creates a real chill. The sub-plot - involving the courtship of Frau Schneider, the lonely landlady, and Herr Schultz, her diffident Jewish suitor - is beautifully played by Sara Kestelman and George Raistrick to show the human cost of Nazism, while the Nazi anthem Tomorrow Belongs to Me chills the blood. Most devastating of all is the show's closing image, when Cumming, grinning like a striptease artist, removes his leather coat to reveal the uniform of a concentration camp victim. It is an extraordinary moment that makes the blood run cold, and you leave this often thrilling show with a shiver.

*   *   *   *   *

It takes some time to realise that Sam Mendes's production of Cabaret has thrown away all those memories we had of Liza Minnelli, whom we had thought of as the definitive Sally Bowles. Indeed, for the first half hour or so this seems to be a muted version with Alan Cumming's Emcee a pale shadow of Joel Grey's malicious grinning clown and Jane Horrocks' Sally Bowles coming across as a washed-out Sloane recovering from a drugs and sex hangover.

But then we begin to realise what Kander and Ebb's musical is really about. It is not the paean of praise to the decadent kind of showbusiness that flourished during the Weimar Republic and was brought to an end by the Nazis, it is about the insidious rise of Nazism itself, pointing up the parallels to the present day, where the spectre is beginning to show itself again across Europe, with its fake promises of prosperity through nationalism, discipline and racial purity.

Though there have been some alterations to the text and a minimalist approach to the piece brought about by economics, it is astonishing how Mendes has changed our perception of this particular musical by building on what is already there. The auditorium itself, not the stage, had become the setting, converted into a night-club that may seem cosy and inviting but becomes sinister the more one examines it. In this atmosphere the songs, which might have been thought merely amusing, become threatening and degrading, each one charged with a relevance, the title song itself being transformed into a hymn of hate and disgust in Horrocks' rendering of it.

The strength of Cumming's portrayal of the Emcee gradually emerges. Like Sally Bowles, he does not seem to be a professional entertainer but an opportunist, a rent boy who has seized the chance to leave the streets, plying his trade through gestures and expressions. At the end, in a startling coup de theatre, he stands revealed as a future victim, a concentration camp prisoner who happens to be both Jewish and gay. The rest of the cast is strong, particularly Sarah Kestelman as the toil-worn landlady who decides against marrying the Jewish fruiterer played by George Raistrick, and Adam Godley as the boyish and likeable Cliff, rapidly politicised when he discovers that his charming friend Ernst (Michael Gardiner) is making use of him.

The four-piece band is augmented throughout the show by members of the cast, descending to floor level for dance routines and dramatic episodes before returning to their saxophones and trumpets.