Alongside former directing partner Guy Ritchie, we have Matthew Vaughn to thank for the resurgence of the British gangster movie after the double-whammy of Lock, Stock and Two Smoking Barrels and Snatch. But since striking out on his own, the one-time producer has surprised those who thought that he was simply Mr Claudia Schiffer, a wealthy journeyman director with an accountant’s eye, no imagination and a Rolodex containing the contact number for every luvvly-jubbly Cockney in film.

With Layer Cake, his first film as a director, Vaughn offered a gripping vehicle for the pre-Bond Daniel Craig and discovered the style icon Sienna Miller. With his follow-up, the soon-to-be released fantasy Stardust, he put Michelle Pfeiffer in a bald wig and persuaded Robert De Niro to do the can-can. And while you’re reading this, he’s prepping a Viking epic that will cost $160 million of Marvel Comics’ money and tell the story of Thor, a god turned superhero. Which, he says blithely, “is pretty far out, if you think about it”.

Stardust, however, is the biggest departure he ever expected to take, an adaptation of a book by the graphic novelist Neil Gaiman. Set in the fairytale village of Wall, it begins with the dorky Tristan (Charlie Cox) courting a haughty local vixen (Sienna Miller) and offering to bring her the debris of a shooting star in exchange for her hand in marriage.

But from here, Tristan finds himself on an incredible adventure. Not only does the fallen star turn out to be a pretty girl (Claire Danes), and a hacked-off one at that, but he and his quarry are captured by pirates and locked in the sights both of a murderous witch, Lamia (Michelle Pfeiffer), and the feuding sons of a dying king.

It sounds exhausting, and it is, even with 70 pages of backstory ripped out of Gaiman’s book and a whole tweaked ending, penned with his co-writer Jane Goldman, the wife of Jonathan Ross. But when we meet in his editing suite, the 36-year-old Vaughn is proud of his film’s anything-goes approach to narrative. “What would you like me to show you?” he asks earnestly. “Romance? Action? Comedy?”

Though its 120 minutes occasionally weigh heavily, Vaughn’s film is an anomaly in today’s marketplace, a film that dares to dream rather than conform to formula. “A book is entitled to meander,” he says, “and that’s the fun of it. You can go off at tangents and spend a lot of time with characters that aren’t necessarily going to keep the narrative driving on.

“Which is funny, because some of the criticisms we’ve had, especially in Hollywood, are that we need a bit more pace: bang, bang, bang. And if we’d decided to get rid of the love story between Tristan and the fallen star, we could have turned it into a 90-minute action adventure. But I wanted to be a bit more whimsical.”

Luckily for Vaughn, his two big hitters came in right at the beginning, with De Niro agreeing straightaway to the role of Captain Shakespeare, a vicious pirate with a shocking secret. “There were two actors I had in mind for that role,” he says. “De Niro and Jack Nicholson. All I cared about was that I wanted an iconic tough guy, mentor and father figure playing a big tough pirate. An agent rang me up to pitch Stephen Fry for the role. Now, I think he’s fabulous; he’s witty, charming and intelligent — but in that role?”

Vaughn admits it was “a mindf***” once De Niro became involved, calling him at weekends to go through the script. “Every weekend, with me playing all the roles,” he recalls. “I’m not an actor so it was slightly embarrassing at first, but then I got into it.” And he brazened it out, too, with co-star Michelle Pfeiffer, an actress not best known for her sympathetic ways. “I wanted Michelle because she’s such an iconic beauty,” he explains, “so it would be a shock to see her fall apart. And she still looks so amazingly beautiful that you could believe her wanting to rip someone’s heart out to maintain her youth, as Lamia does.”

Interestingly, though, although Hollywood gave him the keys to the candy store, Vaughn dug his heels in when it came to casting his hero, the unworldly Tristan. “I always knew Tristan had to be an unknown. You are supposed to share his sense of awe. I’ve been lucky enough with my movies that the majority of people I’ve used became famous afterwards.”

For Tristan’s love interest, the fallen star Yvaine, Vaughn chose the former child star Claire Danes, perhaps his bravest choice. “Some of the people the studio wanted were great,” says Vaughn, “but they were wrong.

“Now, they didn’t ask for these people, but let’s just say that if Yvaine was played by Angelina Jolie or Jessica Alba, and we have this geeky kid who goes off on a mission and meets this hot girl... He’d forget his mission. I would! Now I’m not saying Claire’s not beautiful but she’s quite... unique looking, let’s say, and quirky. And that’s what I wanted. I wanted this film to be about not always going for the hot girl — it’s about falling in love for real.”

Hollywood values don’t dazzle Vaughn. “It is much harder to make a great film with hardly any money and no special effects,” he says, “just a bunch of actors, telling a story. That is a skillset I don’t think many people have. Spectacle is not as hard to create as drama. I think in Hollywood they are starting to forget that.

“What I’m most proud of with Stardust,” he says, “is that, although it’s a big-budget Hollywood film, it’s kept all the film-making qualities that are important to us over here. Normally, the bigger you get, those widgets start taking over very quickly.”

He catches himself. “Does that make any sense?” he asks earnestly. After all this talk of pirates, witches and Vikings, surprisingly, it does.

Stardust is released nationwide on October 19

Explore Film

• Film Reviews

• DVD

• Oscars

• Bollywood

Editor's choice

• The End: the worst movie endings ever
• Introducing The Times Proms Podcast
• Heath Ledger tipped for Oscar