SO HERE IS SIR SALMAN Rushdie, Booker heavyweight, walking political symbol, peculiarly liberated by his new book. The Enchantress of Florence is resolutely not of this world, a novel that is also a work of historical research with a long bibliography. The book rolls lusciously from harem to brothel to the courtesans of Renaissance Florence via the excesses of the Mughal empire - and it allows Rushdie to let rip.

Knighted by the British last year and still benighted by the Iranian Ayatollah's fatwa lurking in the background 20 years after the publication of The Satanic Verses, Rushdie became a human shrine to freedom of speech, whose persecution - had we properly understood it then - signalled more sinister events to come.

Now, however, he does not want to talk about current affairs. Instead, his interests lie in the affairs of a Renaissance man. “I'm feeling less political than I used to,” says Rushdie. “I've spent so much of my life talking about these issues which take on the times we live in very directly. I've had enough of that for a bit.” He pauses, grins. “But never say never.”

Rushdie lolls in easy-fit jeans and an old jumper in the offices of his famously hard-nosed literary agent, Andrew “The Jackal” Wylie. We are in London's Bedford Square, where Rushdie's first novel was accepted long ago by Cape. Rushdie hopes that his literary life will return to those days of equanimity: “I feel I have been damaged as a writer by the way people perceive my work as part of a political event. It is seen as a political entity rather than an artistic one. When Midnight's Children and Shame were published, people responded quite differently to my writing. Then there was a real shift in tone, when they said: ‘Oh that was what he was really trying to do!' That is one of the pleasurable things about this new book: the storyteller is not me. I am still a fiction writer underneath all that mess.” He shakes his head, resignedly.

The Enchantress begins, as many fine works of fiction do, with a stranger riding into town. The stranger is a Scheherazade figure, who must tell his story to avoid death, a motif Rushdie understands and often uses. The town in this case is Fatehpur Sikri, an Indian palace city made of red sandstone, guarded by a tower studded with elephant tusks, the folly of the 16th-century Mughal emperor, Akbar. He was an exact contemporary of Elizabeth I. “Every Indian schoolboy is taught the story of these giant figures of the six grand Mughals, the same way as the English are taught the Tudors.”

Akbar was rather liberal for his beheading-centric time, and attempted to unite warring provinces and religions, allowing free debate in his Muslim court. He is still a Bollywood stalwart. “Some of the most popular Indian movies when I was growing up were about Akbar and his queen Jodhabai - it was the Indian equivalent of Gone With The Wind. In the new version just out, though, there is much debate about whether Jodhabai actually existed.”

When Rushdie's research came across the possibility of Jodhabai, the beautiful Hindu queen, being a figment of the emperor's imagination but a still-powerful figure in court, he was delighted: “The discovery of her fictionality was a liberation - if history could make her up then I had some licence to make stuff up too.” Being fictional, she is easily beddable and biddable. Jodha is one of a series of enchantresses, imagined and historical, that populate the novel in India and Florence. “The women in the book are supposed to be erotic. It's about erotic power.”

Rushdie's relish at this comes as a surprise at first, but it turns out that this is only the start of the 61-year-old writer's long romp through the harem, or as he notes of Jodha: “No living woman was as skilled as she at the Peacock's Foot, that delicate manoeuvre: she placed her thumb on his left nipple and with her four other fingers she ‘walked' around his breast, digging in her long nails, her curved clawlike nails...until they left marks resembling the trail left by a peacock as it walks through mud.”

In life, Rushdie was last year divorced from his fourth wife, Padma Lakshmi, an American model-actress-chef 26 years his junior. Now he is dining a lot at The Ivy. But in fiction, he has often held back on the bedding front - until now.

This bibliography, I observe, is a little racy: courtesans of the Italian Renaissance and The Illustrated Kama Sutra, among others. Rushdie beams. “Indeed. I think this is the most sexually explicit book I have ever written. I used to be shy about writing about sex. In Midnight's Children there's almost nothing, a mention of a penis and then he doesn't even use the proper word. There are no explicit sexual descriptions...”

So what has liberated him? “When it is historical, that's different. There's so much of it written about at that time. Yes, there are three or four of these sex compendiums...and I read 'em.” He laughs: “It's not just a paragraph or two, it's pages and pages on nail sex! It's too good to be true.” We discuss the peacock-trail scene, nails tapping around the office table. “Yes,” Rushdie says. “What's interesting about that is because she's imaginary does the emperor do it on himself?”

No doubt this will trouble critics throughout the land. But Rushdie remains intent on drawing back the veil of modesty on the Mughal empire. “Until I studied it I didn't realise how sexualised this world was - the opium dens, the whorehouses, the intoxication. There are whole books dedicated to unguents, encyclopaedias of the stuff, potions for pleasure.” Or as the extract overleaf describes it: “pastes of tamarind or cinnabar, or dry ginger and pepper which, when mixed with the honey of a large bee, gave a woman intense pleasure without requiring much exertion from the man”.

Such recipes are guaranteed to be historically accurate. After boarding at Rugby, Rushdie studied history at Cambridge and as a novelist he still has a very clear sense of what he can and cannot invent. “It would surprise people to know how much was rooted in truth, how little I had to make up.” He says the unusual step of putting a bibliography in a novel was partly so that the curious reader could follow up, and partly “to avoid the sort of accusations made against Ian” - he refers to allegations that Ian McEwan, in his novel Atonement, used the research of another writer without adequate acknowledgment.

There is a marvellous scene in which one emperor sends the body parts of his vanquished enemy to different ends of his realm, then turns the man's skull into a bejewelled drinking goblet. “Roll over Damien Hirst,” Rushdie snorts. “It was so much better than you could make up.”

Akbar's liberal court is all based on truth too. Rushdie calls his debating hall the House of New Worship, where the “wine drinkers” engaged in philosophical and religious debate with the “water drinkers”, plus a brace of Jesuit priests. “The original building in Fatehpur Sikri seems to have disappeared, so I sited the debaters in a tent, an impermanent structure as a metaphor for changing, developing ideas” - the sort of ideas which would be illegal to express in a modern theocracy.

Rushdie's descriptions of the Janissaries, the marines of the Ottoman army, taking the most beautiful, most intelligent, most athletic children away from their conquered enemies and brainwashing them, retraining them as soldiers, has a whiff of the present-day madrassas. “I didn't intend that, but I suppose it's all there. This is a brutal age, this is an age of indoctrination as well, but I kind of hate preachy books, I hate books that say: this is really about the 20th century. Human nature is what it is and if we, knowing about our world, look back at this world, we can see that our ancestors behaved the same way. I don't need to spell out a kind of contemporary connection because we are still the same somewhat unpleasant species.”

After some coruscating and still-painful reviews of his modern New York-based novel, Fury, in 2001, Rushdie's retreat into the past seems both sensible - and perhaps permanent. “I've got a bit of a taste for it now, this kind of writing. I enjoy the discipline of it, using my old education. I've not used my mind in that way for a long time.” He seems almost defensive of his fabulous fable: “My pleasurable funny sexy international story - what's wrong with it?”

Technically, The Enchantress pushes a lot of boundaries. Rushdie has always liked complicated architecture to hold up his plots: The Satanic Verses, he admits, began as three books before it was jigsawed into one.

He also has a taste for the palimpsest, the work of art that overlays another. In The Moor's Last Sigh a Japanese picture restorer dies when the painting she is working on is shot. In The Enchantress, the famed art studio of Fatehpur Sikri is put to work by Akbar to create endless imaginary portraits of the enchantress, the heroine Qara Köz. Rushdie brings the character to life, and the great paintings of the time do the same. The palace falls under the spell of this extraordinary woman, and the painter is so infatuated he fades away into one of his own canvases. I ask Rushdie about this repeating motif. “One of the things my books have explored is the boundary between the real world and the imagined world. That boundary may be softer than we imagine it is. If we think of things just naturalistically, one of the ways in which the world works is that things that are imagined become actual, an invention is like that; so is a nation. Many things which we take for granted began in imagination and became actual, so it is a soft frontier, softer than we think, so I have once or twice had some fun crossing it.”

Rushdie looks somehow embarrassed. “Another problem of having written a lot of books is you don't always remember what you've written before...”

“And you have ingrained habits?”

“Habits, yes. And afterwards people say you've done this kind of thing before and you think: f**k!” He is more modest and self-deprecatory than the chattering and critiquing classes give him credit for. Rushdie has, after all, had his share of knocks, misunderstandings and uprootings. He divides his time between London and New York, where until recently, he shared an apartment with Lakshmi. But his son Milan - “not yet 11” - lives with his third wife Elizabeth West in London, and his older son, Zafar, 28, whose mother was the late Clarissa Luard, is also here.

And although Rushdie dislikes heavy-handed connections between his fiction and fact, his Enchantress character, Qara Köz, is always being uprooted too. “The way in which she makes relationships is very provisional. There's a thing that she holds back. She has a difficulty putting down roots in other people, a difficulty with the idea of permanence.”

I also wonder about Rushdie's peculiar obsession with Machiavelli, who has a splendid walk-on role in the Florence part of the book. It shows Machiavelli as a carefree youth, as the life of the party, and as an older man, after he is exiled by the Medicis. He isn't at all Machiavellian, is he? “He's had such a bad press,” says Rushdie. “Sneaky, devious...but the portrait of him in my book is quite different. The Prince is misread - it's a parody of the hagiographic literature of the time, a criticism of power politics in Italy.” And as Machiavelli sits exiled and isolated, writing his great (yet unpublished) work, you can't help but think: there goes another misunderstood author putting out his iconoclastic message.

Perhaps Rushdie is now shying away from messages, at least consciously. His early books are more, rather than less, resonant. He shrugs. “People say ‘the news agenda has come round to you now' and I think: I told you so. We are interested in it now, when of course if you grew up in India or Pakistan, you were interested in it anyway - as immigrants into the West.”

We talk about the challenges of writing post-September 11, post-Iraq war: subjects that Rushdie is not dealing with - for the moment. He liked Jonathan Safran Foer's book about a son losing his father in the twin towers, but thinks that the book would have been as good without the September 11 backdrop. He liked DeLillo's Falling Man. “But when you think that War and Peace was written 60 years after the event, and that's where you go for the definitive account, then maybe our war books have still to come.”

In this new book, Rushdie has also moved away from what the New Yorker critic James Wood has described as “hysterical realism”, a step beyond magical realism that attempts to convey the raucousness of contemporary life through outlandish proliferating plots, allegory, bizarre coincidence and high irony. Authors such as Thomas Pynchon, Zadie Smith, David Foster Wallace and Don DeLillo are accused along with Rushdie. “If that's ‘hysterical realism' I'm proud to be on that team.”

The Enchantress of Florence by Salman Rushdie
Jonathan Cape, £18.99; 368pp

Explore Books

• Book Extracts

• Book Reviews

• Books Group

Times Recommends

• The Gone-Away World by Nick Harkaway
• Burning is too good for them
• Strange Fruit: Why Both Sides Are Wrong in the Race Debate by Kenan Malik